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

思路

和其它的树相关的题目一样，这道题也可以考虑用DFS来进行搜索。在搜索的过程中，递归地判断左右子树是否符合对称条件。

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if (root):
            return self.Symmetric(root.left, root.right)
        else:
            return True
    
    def Symmetric(self, left, right):
        if (left and right):
            if (left.val == right.val):
                return self.Symmetric(left.left, right.right) and self.Symmetric(left.right, right.left)
            else:
                return False
        elif (left is None and right is None):
            return True
        else:
            return False