Code & Func

第48天。

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:

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

刚看的时候还有点懵，要怎么递归的去求解这种问题呢，要比较的两个节点隔得有点远啊。后来是上课时突然想到对称其实和根节点的左子树和右子树有关，我们把他当成两个树来求解就好了，递归时需要两个TreeNode:

1
def isSymmetric1(self, root):
2
    """
3
    :type root: TreeNode
4
    :rtype: bool
5
    """
6
    if root is None:
7
        return True
8
    else:
9
        return self.isSymmetricRec(root.left,root.right)
10

11
def isSymmetricRec(self,left,right):
12
    """
13
    :type left: TreeNode
14
    :type right: TreeNode
15
    :rtype: bool
9 collapsed lines
16
    """
17
    if left is None and right is None:
18
        return True
19
    elif left is not None and right is not None:
20
        return left.val == right.val \
21
                and self.isSymmetricRec(left.left,right.right) \
22
                and self.isSymmetricRec(left.right,right.left)
23
    else:
24
        return False

然后是迭代解，这里是用层次遍历去做的：

1
def isSymmetricBFS(self,root):
2
    """
3
    :type root:TreeNode
4
    :rtype: bool
5
    """
6
    if root is None:
7
        return True
8

9
    leftqueue = Queue()
10
    rightqueue = Queue()
11

12
    leftqueue.put(root.left)
13
    rightqueue.put(root.right)
14

15
    while not leftqueue.empty():
14 collapsed lines
16
        left = leftqueue.get()
17
        right = rightqueue.get()
18
        if left is None and right is None:
19
            continue
20
        elif left is not None and right is not None:
21
            if left.val != right.val:
22
                return False
23
            leftqueue.put(left.left)
24
            leftqueue.put(left.right)
25
            rightqueue.put(right.right)
26
            rightqueue.put(right.left)
27
        else:
28
            return False
29
    return True

然后是在dicuss中看到的c++解法，思路其实是一样的：

1
bool isSymmetric(TreeNode *root) {
2
    if (!root) return true;
3
    return helper(root->left, root->right);
4
}
5

6
bool helper(TreeNode* p, TreeNode* q) {
7
    if (!p && !q) {
8
        return true;
9
    } else if (!p || !q) {
10
        return false;
11
    }
12

13
    if (p->val != q->val) {
14
        return false;
15
    }
3 collapsed lines
16

17
    return helper(p->left,q->right) && helper(p->right, q->left);
18
}

1
bool isSymmetric(TreeNode *root) {
2
    TreeNode *left, *right;
3
    if (!root)
4
        return true;
5

6
    queue<TreeNode*> q1, q2;
7
    q1.push(root->left);
8
    q2.push(root->right);
9
    while (!q1.empty() && !q2.empty()){
10
        left = q1.front();
11
        q1.pop();
12
        right = q2.front();
13
        q2.pop();
14
        if (NULL == left && NULL == right)
15
            continue;
11 collapsed lines
16
        if (NULL == left || NULL == right)
17
            return false;
18
        if (left->val != right->val)
19
            return false;
20
        q1.push(left->left);
21
        q1.push(left->right);
22
        q2.push(right->right);
23
        q2.push(right->left);
24
    }
25
    return true;
26
}