首页 > itarticle > symmetric tree

symmetric tree

admin 11月 12, 2020 0

The Question

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

The Answer

没什么好说的，遍历比较就可以了。就是平常的p->left,q->left变成了p-left,q->right

The Key

树都为空的情况；
遍历时候，一个为空了，一个还没有的情况；
递归调用的时候，到了第三层，就需要两边递归，中间递归。

代码如下

class Solution {
public:
    bool (TreeNode* root) {
        if(!root)return true;
        return search(root->left,root->right);
    }
    bool search(TreeNode* p,TreeNode* q){
        if(!p&&!q)return true;
        else if(!p||!q)return false;
        
        if(p->val!=q->val)return false;
        else return search(p->left,q->right)&&search(p->right,q->left);
    }
};

~Thanks~
By 海天游草~~~2017.3.15