题目

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

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        return is(pRoot,pRoot);
    }
    bool is(TreeNode* p1,TreeNode* p2)
    {
        if(p1==NULL&&p2!=NULL) return false;
        if(p1!=NULL&&p2==NULL) return false;
        if(p1==NULL&&p2==NULL) return true;
        if(p1->val==p2->val)
        {
            return is(p1->left,p2->right);
        }
        return false;
    }
};

思路

当以中右左的顺序和中左右的顺序遍历二叉树都得到相同的结果时就是对称的了。

接下来就是怎么写递归的问题了。这里等于NULL要单独列出来，因为有一种情况是

7 7 7 7 7 7 三层，分别按顺序1个，2个，3个数字，是不对称的，所以要把NULL也算上。