【Leetcode】【python】Symmetric Tree 对称二叉树

题目大意

判断一个树是否左右对称

解题思路

非递归解法

按层遍历,每一层检查一下是否对称。

递归解法

其中左子树和右子树对称的条件:
两个节点值相等,或者都为空
左节点的左子树和右节点的右子树对称
左节点的右子树和右节点的左子树对称

代码

递归(清晰易懂版)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def judge(self, p, q):
if p == None and q == None:
return True
if p and q and p.val == q.val: # 如果一边有一边没有那么直接返回False
return self.judge(p.left, q.right) and self.judge(p.right, q.left)
return False

def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root:
return self.judge(root.left, root.right)
return True

递归(超简洁版)

运算速度慢

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
def isSym(L,R):
if L and R and L.val == R.val:
return isSym(L.left, R.right) and isSym(L.right, R.left)
return L == R
return isSym(root, root)

迭代

换成数组进行判断,运算速度只超过0.5%的人

1
2
3
4
5
6
7
8
class Solution(object):
def isSymmetric(self, root):
queue = [root]
while queue:
values = [i.val if i else None for i in queue]
if values != values[::-1]: return False
queue = [child for i in queue if i for child in (i.left, i.right)]
return True

总结

递归与迭代的关系

1) 递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。
2) 能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出.

函数嵌套

python允许函数嵌套,也就是说我们可以在函数内部定义一个函数,这些函数都遵循各自的作用域和生命周期规则。