Description

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:

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

But the following [1,2,2,null,3,null,3] is not:

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

Note:
Bonus points if you could solve it both recursively and iteratively.

 

Solution

先判断根节点是否为空，根节点是否有左子树和右子树。

若根节点同时有左子树右子树，分布用两个数组维护左子树和右子树在同一层上的节点情况，并检查当前层上的节点的对称性。

每次根据当前层的情况，产生下一层，产生过程类似层序遍历。

 

Caution

1.当节点只有左子树或右子树，产生下一层时要用NULL填补没有子树的一边。

2.检查对称性时，不仅要检查左边节点a的值与右边相应节点b的值是否相等，还要检查a的孩子情况与b的孩子情况是否相等。

 

Code

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
public:
    vector<TreeNode*> getChilds(vector<TreeNode*>& fathers, bool& isEnd)
    {
        vector<TreeNode*> ret;
        for(int i = 0; i < (int) fathers.size(); i++)
        {
            if(fathers[i] == NULL) continue;
            if(fathers[i]->left)
            {
                isEnd = false;
                ret.push_back(fathers[i]->left);
            }
            else
            {
                ret.push_back(NULL);
            }
            if(fathers[i]->right)
            {
                isEnd = false;
                ret.push_back(fathers[i]->right);
            }
            else
            {
                ret.push_back(NULL);
            }
        }
        return ret;
    }
    bool check(vector<TreeNode*>& left, vector<TreeNode*>& right)
    {
        if(left.size() != right.size()) return false;
        int i, j;
        for(i = 0, j = left.size() - 1; i < (int)left.size() && j >= 0; i++, j--)
        {
            if(left[i] == NULL && right[j] == NULL) continue;
            if(left[i] == NULL && right[j] != NULL) return false;
            if(left[i] != NULL && right[j] == NULL) return false;
            if(left[i]->val != right[j]->val) return false;
        }
        return true;
    }
    bool isSymmetric(TreeNode* root)
    {
        if(!root) return true;
        if((!root->left && root->right) || (root->left && !root->right)) return false;
        bool ret = true;
        vector<TreeNode*> lfathers, rfathers;
        lfathers.push_back(root->left);
        rfathers.push_back(root->right);
        while(ret)
        {
            if(!check(lfathers, rfathers)) return false;
            bool lend = true;
            bool rend = true;
            vector<TreeNode*> lchilds = getChilds(lfathers, lend);
            vector<TreeNode*> rchilds = getChilds(rfathers, rend);
            if(lend != rend) return false;
            if(lend == true && rend == true) break;
            lfathers.clear();
            rfathers.clear();
            lfathers.assign(lchilds.begin(), lchilds.end());
            rfathers.assign(rchilds.begin(), rchilds.end());
        }
        return ret;
    }
};