题解 | #判断二叉树是否对称#

解题思路

• 本题判断二叉树是否对称，要通过对二叉树的层序遍历来实现，即通过层序遍历来判断当前状态是否满足对称，并进入下一层判断，是较为典型的BFS。
• 根据题目备注所提示的，这里给出递归以及迭代两种解法。
• 题目相对要注意的地方在于，是在于对节点的访问顺序，即如何满足对称的条件，示意图如下：

方法一：递归

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool isSymmetric(TreeNode* root) {
        // write code here
        if(root==nullptr)
            return true;
        return help(root->left,root->right);
    }

    //辅助递归函数，参数为两节点，判断两节点是否当前值相等且子节点满足对称。
    bool help(TreeNode* left,TreeNode* right){
        //判断left和right有可能为空指针的情况
        if(!left&&!right)
            return true;
        //其中有一个节点不存在，或者两节点值不等，则返回false
        if((!left||!right)||(left->val!=right->val))
            return false;
        //递归调用判断
        return help(left->left,right->right)&&help(left->right,right->left);        
    }
};

复杂度分析：

时间复杂度：O(n)，n为节点数量，每个节点访问一次。
空间复杂度：O(n)，来源于递归使用的栈空间，递归次数是n的级别。

方法二：迭代

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    bool isSymmetric(TreeNode* root) {
        // write code here
        if(root==nullptr)
            return true;
        //队列q按序存储每次需要判断的两节点。left,right相邻
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while(!q.empty()){
            TreeNode* l=q.front();
            q.pop();
            TreeNode* r=q.front();
            q.pop();
            //与方法一中的判断方式相同
            if(!l&&!r)
                continue;
            if((!l||!r)||(l->val!=r->val))
                return false;
            //按照满足对称要求的方式进行两两组合,保证下次pop出来的l,r是需要判断的一对节点。
            q.push(l->left);
            q.push(r->right);

            q.push(l->right);
            q.push(r->left);
        }
        return true;
    }
};

复杂度分析：

时间复杂度：O(n)，同上。
空间复杂度：O(n)，来源于队列中的节点数量，不超过n。