100/101/572. 相等树/镜像树/树的子结构

• 100 相等树
  思路：1. 先思考常规情况，pq均不为None；2. 再思考退出条件，pq至少一个为None。

    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        # 左右都没有val的情况
        if not p and not q:
            return True
        # 左右有一个没有val的情况
        if not p or not q:
            return False
        # 左右都有val的情况
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.rihgt)

• 101 镜像树

1. 镜像的条件是左孩子的值和右孩子的值相等，且左孩子的左孩子和右孩子的右孩子镜像，且左孩子的右孩子和右孩子的左孩子镜像。
2. 退出条件为左孩子或者右孩子至少有一个为None
3. 构造一个辅助函数，传参为左子树和右子树。

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

    def isSymmetricHelper(self, left, right):
        # 左右两棵树都为None的情况
        if not left and not right:
            return True
        # 左右两棵树有一个为None的情况
        if not left or not right:
            return False
        # 左右两棵树都不为None的情况
        return left.val == right.val and self.isSymmetricHelper(left.left, right.right) and self.isSymmetricHelper(left.right, right.left)

• 572 树的子结构
  写一个compare的辅助函数，compare要求两棵树完全一致，不能有多余的结点。例如[1,2,3]和[1,2]不一致。compare本身也是递归函数。
  判断子结构的函数是递归函数，通用判断条件为s和t一致，或者s的孩子和t一致。

    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        if not s and not t:
            return True
        if not s or not t:
            return False
        return self.compare(s,t) or self.isSubtree(s.left,t) or self.isSubtree(s.right,t)

    def compare(self, s, t):
        if not s and not t:
            return True
        if not s or not t:
            return False
        return s.val == t.val and self.compare(s.left, t.left) and self.compare(s.right, t.right)