关于树的recursion

在写树的递归时，关键注意解决完当前节点问题后，剩余子问题是否和原问题性质一致只是规模减少。
比如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