题目描述

给定一个二叉树，检查它是否是镜像对称的。

样例

 

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

算法1

(不清晰思路) $O(n^2)$

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        stack<TreeNode*> L, R;
        TreeNode *p = root->left, *q = root->right;
        while(p && q || !L.empty() || !R.empty()){
            while(p || q){  //应该把所有的元素都考虑进去，这样当不一样的时候，表明不对称,这里时pq两个都不等于null 或者 都等于null。。 不太对。  正确的思想应该是，当他们有一个是空，另一个不是，直接判断false
                L.push(p);
                p = p->left;
                R.push(q);
                q = q->right;
            }
            p = L.top();L.pop();
            q = R.top();R.pop();
            if(p->val != q->val) return false;

            p = p->right;
            q = q->left;
            if((!q || !p) && q != p) return false; 
        }
        return true;
    }
};

算法2

(ycx) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == nullptr) return true;
        stack<TreeNode*> L, R;
        TreeNode *p = root->left, *q = root->right;
        while(p || q || !L.empty() || !R.empty()){
            while(p && q){   
                L.push(p);
                p = p->left;
                R.push(q);
                q = q->right;
            }//此处说明  两者都null 或者 有一个时null
            if(p || q) return false;   //到这里，说明有一个是空
            p = L.top();L.pop();
            q = R.top();R.pop();
            if(p->val != q->val) return false;
            p = p->right;
            q = q->left;

        }
        return true;
    }
};

//递归写法
class Solution {
public:
    bool dfs(TreeNode* left, TreeNode*right){
        if((left && !right) || (!left && right)) return false;
        if(!left && !right) return true;
        if(left->val != right->val) return false;
        return dfs(left->left, right->right) && dfs(left->right, right->left);
    }
    bool isSymmetric(TreeNode* root) {
        return dfs(root->left, root->right);
    }
};