LeetCode 100 相同的数：

给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

解题思路：

1. 判断空集
2. 若非空， 判断当前节点的同时，递归树的左子数和右子数

代码

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        if q is None and p is None:
            return True
        elif q is not None or p is not None:
            return q.val == p.val and self.isSameTree(p.left, q.left) \
                   and self.isSameTree(p.right,  q.right)

LeetCode 101 对称树：

给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

解题思路

1. 判断空集
2. 若非空，与上一题类似，只不过要判断左子数和右子数是否相等

代码

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def isSymmetric(self, root):
        """
        1. 时间复杂度：O(n)
        2. O(n)，因为我们遍历整个输入树一次，所以总的运行时间为O(n)，
        其中n是树中结点的总数。
        3. 空间复杂度：递归调用的次数受树的高度限制。在最糟糕情况下，
        树是线性的，其高度为O(n)。
        4. 因此，在最糟糕的情况下，由栈上的递归调用造成的空间复杂度为O(n)
        """
        root1 = root
        root2 = root
        return self.isMirror(root1, root2)
    def isMirror(self, root1, root2):
        if root1 is None and root2 is None:
            return True
        if root2 is not None and root2 is not None:
            return root1.val == root2.val and self.isMirror(root1.left, root2.right) \
                   and self.isMirror(root1.right, root2.left)