剑指offer - 对称的二叉树

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/ff05d44dfdb04e1d83bdbdab320efbcb

题意

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

题解

递归。

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)
    {
        if(pRoot==NULL) return true;
        return isSame(pRoot->left,pRoot->right);
    }

    bool isSame(TreeNode * left,TreeNode * right){
        if(left==NULL&&right==NULL)
            return true;
        if(left!=NULL&&right!=NULL)
            return left->val==right->val&&
                isSame(left->left,right->right)&&
                isSame(left->right,right->left);
        return false;
    }
};

顺便贴上建树的代码，建树是按照二叉树层次遍历的思想来建的。
例如树对应的序列为：A B C D E F x x x G H x I
表示的树如下图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
TreeNode * build(string seq){
    if(seq==""||seq[0]=='#') return NULL;
    int index = 0;
    TreeNode * root  = new TreeNode(seq[index++]-'0');
    queue<TreeNode *> que;
    que.push(root);
    while(index<seq.size()){
        TreeNode * top = que.front();
        que.pop();
        if(isdigit(seq[index])){
            top->left = new TreeNode(seq[index++]-'0');
            que.push(top->left);
        }else if(seq[index]=='#'){
            index++;
            top->left = NULL;
        }
        if(index>=seq.size()) break;

        if(isdigit(seq[index])){
            top->right = new TreeNode(seq[index++]-'0');
            que.push(top->right);
        }else if(seq[index]=='#'){
            index++;
            top->right = NULL;
        }
    }
    return root;
}