在写树的递归时，关键注意解决完当前节点问题后，剩余子问题是否和原问题性质一致只是规模减少。
比如Symmetric Tree 问题，比较树是否对称， 定义一个helper方程，输入为两个root节点，输出为检测两个树是否对称。当我们检测完当前树的值相同之后，剩下的四个节点（分别为连个root节点的左右孩子，一共四个）可分为两组，性质相同，规模变小。
# 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
"""
def helper(left, right):
if not left and not right:
return True
if not left or not right:
return False
if left.val != right.val:
return False
return helper(left.left, right.right) and helper(left.right, right.left)
if not root:
return True
return helper(root.left, root.right)
也可以使用bfs 解决
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if not root:
return True
q1 = [root.left]
q2 = [root.right]
while q1 and q2:
top1 = q1.pop(0)
top2 = q2.pop(0)
if not top1 and not top2:
continue
if not top1 or not top2:
return False
if top1.val != top2.val:
return False
# from left to right
q1 += [top1.left, top1.right]
# from right to left
q2 += [top2.right, top2.left]
return True
e101 Symmetric Tree
