题解 | #对称的二叉树#

方法一：迭代解法（利用队列）

思路： 考虑bfs中，队列的特性，可以每次出队两个节点、入队两个节点，为了方便起见，根节点首先入队两次即可.

• 代码如下：

class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot) {
        if(pRoot==nullptr) return true;
        queue<TreeNode*> que;
        que.push(pRoot);que.push(pRoot);
        while(!que.empty()){
            TreeNode* node1=que.front();
            que.pop();
            TreeNode* node2=que.front();
            que.pop();
            if(node1->val!=node2->val) return false;
            if(node1->left!=nullptr && node2->right!=nullptr){
                que.push(node1->left);
                que.push(node2->right);
            }
            else if(node1->left || node2->right) return false;
            if(node1->right!=nullptr && node2->left!=nullptr){
                que.push(node1->right);
                que.push(node2->left);
            }
            else if(node1->right || node2->left) return false;
        }
        return true;
    }
};

方法二：递归解法

思路很简单，分别递归两边的子树节点，判断值是否相等即可。

• 代码如下：

class Solution {
public:
    bool IsSy(TreeNode* root1,TreeNode* root2){
        if(root1==nullptr && root2==nullptr) return true;
        if(root1!=nullptr && root2!=nullptr && root1->val==root2->val){
            return (IsSy(root1->left, root2->right) && IsSy(root1->right, root2->left));
        }
        return false;
    }
    bool isSymmetrical(TreeNode* pRoot) {
        if(pRoot==nullptr) return true;
        return IsSy(pRoot->left, pRoot->right);
    }
};