Leetcode 101 - Symmetric Tree

DocumentsAlgorithms
Algoroithms, Leetcode, Python
Catalogue
  1. 1. Question
  2. 2. Analysis
  3. 3. Code

Question

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.

Analysis

要判断一个树是否对称，就是看同一层的节点是否关于中心对称。例如一层有8个节点，则应该有第一个节点值等于第八个节点值，第二个节点值等于第七个…因此在使用循环或者递归遍历树的的时候，应当使得每一步比较的两个节点位置关于中心对称。因此从每次向下遍历时，应当把每一层首位对应的两个节点送到下一步进行比较，而不是简单地把一个节点的左右子节点送到下一步。

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
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """       
        # Iterate (Beat 100%)
        if root == None:
            return True
        stack = [root.left, root.right]
        while(stack):
            p, q = stack.pop(), stack.pop()
            if p == None and q == None:
                continue
            if p == None or q == None or p.val != q.val:
                return False

            stack.extend([p.left, q.right, p.right, q.left])
        return True        

        # Recursive
#         if root == None:
#             return True
#         return self.isSymmetricAssist(root.left, root.right)
        
#     def isSymmetricAssist(self, left, right):
#         """
#         :type left: TreeNode
#         :type right: TreeNode
#         :rtype: bool
#         """
#         if left == None or right == None:
#             return left == right
#         if left.val != right.val:
#             return False
#         return (self.isSymmetricAssist(left.left, right.right) and 
#             self.isSymmetricAssist(left.right, right.left))
Comments