LeetCode 572. 另一棵树的子树

题目

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

例：
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

方法：递归

整体思路为在第一棵二叉树 root 中寻找与第二棵二叉树 subRoot 的根节点的值相同的结点，然后以此节点为基础进行判断是否包含，若不包含则继续寻找下一个相同的，直至遍历完第一棵二叉树或确定包含

• 主要部分：首先要判断第一棵二叉树（或其子树）和第二棵二叉树是否为空，若其中之一为空，即两个树不同。然后判断两棵树（子树）根节点的值是否相等，若相等并且第一棵树（子树）在结构和数值上均与第二棵树相同，那么表示存在；若不相等，则需要继续递归，寻找合适的节点
• 比较部分：同 100. 相同的树

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSubtree(self, root, subRoot):
        if root == None and subRoot == None:
            return True
        elif root == None or subRoot == None:
            return False
        if root.val == subRoot.val and self.compare(root, subRoot) == True:
            return True
        else:
            return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

    def compare(self, p, q):
        if p == None and q != None:
            return False
        elif p != None and q == None:
            return False
        elif p == None and q == None:
            return True
        elif p.val != q.val:
            return False

        left = self.compare(p.left, q.left)
        right = self.compare(p.right, q.right)
        return left and right