LeetCode 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
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

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

分析

判断树是否是对称的

代码

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
# 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):
'''
Basically, this question is recursively. Or we can say, the tree structure is recursively, so the recursively solution maybe easy to write:
TC: O(b) SC: O(log n)
'''
# recursively
def isSymmetric1(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root is None:
return True
else:
return self.isMirror(root.left, root.right)
def isMirror(self, left, right):
if left is None and right is None:
return True
if left is None or right is None:
return False
if left.val == right.val:
outPair = self.isMirror(left.left, right.right)
inPiar = self.isMirror(left.right, right.left)
return outPair and inPiar
else:
return False
# The essence of recursively is Stack/Queue, so we can use our own stack to rewrite it into iteratively:
# iteratively
def isSymmetric(self, root):
if root is None:
return True
q = [[root.left, root.right]]
while len(q) > 0:
pair = q.pop(0)
left = pair[0]
right = pair[1]
if left is None and right is None:
continue
if left is None or right is None:
return False
if left.val == right.val:
q.append([left.left, right.right])
q.append([left.right, right.left])
else:
return False
return True

点评

递归版本相当于是深度优先遍历,每次递归的时候传递的参数是左子树根节点和对称的右子树根节点,每次递归返回的是这两棵子树是否是对称的,返回条件是某棵/两棵子树为空,每次递归的时候会首先判断这两棵子树的根节点值是否相同,然后分别判断两个根节点对应的两对子树是否都对称

迭代版本相当于是广度优先遍历,迭代之前会有一个队列/列表存储需要遍历的左右子树,迭代这个队列,直到为空,每次迭代的时候取出队列里的一对子树,比较是否相等,然后分别将左右子树的两对根节点放入队列,进行下一次迭代