剑指28：对称的二叉树

传送门

nowcoder
leetcode

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。
注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

C++ 代码 - nowcoder

/*
    递归实现
*/
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if (pRoot == nullptr) return true;
        return isSymmetricalCore(pRoot->left, pRoot->right);
    }

    bool isSymmetricalCore(TreeNode* node1, TreeNode* node2) {
        if (node1 == nullptr && node2 == nullptr) return true;
        if (node1 == nullptr || node2 == nullptr) return false;
        if (node1->val != node2->val) return false;
        return isSymmetricalCore(node1->left, node2->right)
            && isSymmetricalCore(node1->right, node2->left);
    }
};

C++ 代码 - leetcode

/*
	递归实现
*/
class Solution {
public:
    bool checkSymmetricTree(TreeNode* root) {
        if (!root) return true;
        return dfs(root->left, root->right);
    }

    bool dfs(TreeNode* node1, TreeNode* node2) {
        if (!node1 && !node2) return true;
        if (!node1 || !node2 || node1->val != node2->val) return false;
        return dfs(node1->left, node2->right)
            && dfs(node1->right, node2->left);
    }
};

/*
	迭代实现：使用队列
*/
class Solution {
public:
    bool checkSymmetricTree(TreeNode* root) {
        if (!root) return true;
        
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while (!q.empty()) {
            TreeNode* leftNode = q.front(); q.pop();
            TreeNode* rightNode = q.front(); q.pop();
            // 左节点为空且右节点为空，说明此时是对称的
            if (!leftNode && !rightNode) continue;
            // 左节点/右节点至少一个不为空，或左节点/右节点不为空但是值不相等
            if (!leftNode || !rightNode || (leftNode->val != rightNode->val)) {
                return false;
            }

            q.push(leftNode->left);
            q.push(rightNode->right);
            q.push(leftNode->right);
            q.push(rightNode->left);
        }

        return true;
    }
};