leetcode解题: Symmetric Tree (101)

发表于 | 分类于

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 2
/ \ / \
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2 2
\ \
3 3

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

解法1：Recursive

主要还是分治的思想，对称的意思就是left = right，实际上我们要比较的是left tree 和right tree。
需要满足的条件是left.left = right.right && left.right = right.left
然后不停的递归下去就可以了。
C++

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
/**
 * 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 == NULL) {
            return true;
        }
        if (root->left == NULL && root->right == NULL) {
            return true;
        }
        return mirror(root->left, root->right);
    }
    bool mirror(TreeNode* left, TreeNode* right) {
        if (left == NULL && right == NULL) {
            return true;
        }
        if (left != NULL && right == NULL) {
            return false;
        }
        if (left == NULL && right != NULL) {
            return false;
        }
        if (left->val != right->val) {
            return false;
        }
        bool leftChild = mirror(left->left, right->right);
        if (!leftChild) return false;
        bool rightChild = mirror(left->right, right->left);
        return rightChild;
    }
};

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetric(root.left, root.right);
    }
    private boolean isSymmetric(TreeNode left, TreeNode right) {
        if (left != null && right == null) {
            return false;
        }
        if (left == null && right != null) {
            return false;
        }
        if (left == null && right == null) {
            return true;
        }
        if (left.val != right.val) return false;
        return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
    }
}

解法2：Iteratively

非递归一般需要用额外的数据结构，这里可以想到的是用queue，然后做一个BFS（按层遍历）。和比较是否是same tree很像，唯一不一样的是这里left需要从左往右，而right需要从右往左。
参考了喜唰唰的解法。
C++

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
/**
 * 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*> left, right;
       left.push(root->left);
       right.push(root->right);
       while(!left.empty() && !right.empty()) {
           TreeNode* lchild = left.front();
           TreeNode* rchild = right.front();
           left.pop();
           right.pop();
           if (!lchild && !rchild) continue;
           if (!lchild && rchild) return false;
           if (lchild && !rchild) return false;
           if (lchild->val != rchild->val) return false;
           left.push(lchild->left);
           left.push(lchild->right);
           right.push(rchild->right);
           right.push(rchild->left);
       }
       if (!left.empty() || !right.empty()) {
           return false;
       }
     return true;
    }
};

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        if ((root.left != null && root.right == null) || (root.right != null && root.left == null)) {
            return false;
        }
        if (root.left == null && root.right == null) return true;
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            if (queue.size() % 2 != 0) return false;
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if ((left.left != null && right.right == null) || (left.left == null && right.right != null)) return false;
            if ((left.right != null && right.left == null) || (left.right == null && right.left != null)) return false;
            if (left.val != right.val) return false;
            if (left.left != null) {
                queue.offer(left.left);
                queue.offer(right.right);
            }
            if (left.right != null) {
                queue.offer(left.right);
                queue.offer(right.left);
            }
        }
        return true;
    }
}