101. Symmetric Tree

发表于 | 分类于 | |

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
6
7
>     1
>    / \
>   2   2
>  / \ / \
> 3  4 4  3
>
>

>

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

1
2
3
4
5
6
7
>     1
>    / \
>   2   2
>    \   \
>    3    3
>
>

>

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

题意：判断一棵树是否镜面对称。

​ 因为前不久刚做了个二叉树的小结 ，知道了做二叉树大概的套路：

  1. 判断空值
  2. 处理节点
  3. 递归处理左子树和右子树（其实就是分解成子问题）

​ 然而，竟然思索了一会没有想到递归的解法。因为我想分解成左子树和右子树也分别镜面对称，但是结合样例就知道看起来不对啊。

​ 但是发现非递归的解法，就是层序遍历，然后每一层都是回文的。但是有个细节需要注意就是空值，所有的空的地方我都人为地用-1来替代了。

​ 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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    bool isSymmetric(TreeNode *root)
    {
        if (!root)
            return true;
        queue<TreeNode *> qTree;
        vector<int> v;
        qTree.push(root);
        int len;
        TreeNode *node;
        int count = 0;//计算-1，即空值的个数
        while (count < qTree.size())
        {
            v.clear();
            count = 0;
            len = qTree.size();
            for (int i = 0; i < len; ++i)
            {
                node = qTree.front();
                qTree.pop();
                if (node)
                {
                    v.push_back(node->val);
                    qTree.push(node->left);
                    qTree.push(node->right);
                    if (!node->left) count += 1;
                    if (!node->right) count += 1;
                } else
                {
                    v.push_back(-1);
                    qTree.push(nullptr);
                    qTree.push(nullptr);
                    count += 2;
                }
            }
            if (isSymmetricVector(v))
                continue;
            else
                return false;
        }
        return true;
    }

    bool isSymmetricVector(vector<int> v)
    {

        int len = v.size();
        for (int i = 0; i < len / 2; ++i)
        {
            if (v[i] != v[len - i - 1])
                return false;
        }
        return true;
    }
};

​ 今早起来看了下Discussion，发现是自己的子问题没有分解好。这里需要借助一个辅助函数，用来判断两棵树是否相同。这样镜面对称就可以这么分解子问题了：

​ 1：两个根值要相同

​ 2：左树的左子树要和右树的右子树相同 并且 左树的右子树要和右树的左子树相同

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
class Solution {
public:
    bool isSymmetric(TreeNode *root)
    {
        if (!root)
            return true;
        return isSymmetric(root->left, root->right);
    }

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