摘要
Title: 572. 另一棵树的子树
Categories: 树

572. 另一棵树的子树

题意

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

思路

暴力匹配即可
优化：只在高度相同时匹配，结合 104. 二叉树的最大深度与 100. 相同的树
1. root 中的所有与 h 高度相同的节点，对应的子树两两不相交，这些子树的节点个数之和不超过 n，所以总的匹配次数也不会超过 n，时间复杂度为 O(n)
2. 先判断 node 的高度是否等于 h ，只有在相等时才做匹配。

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        
        def dfs1(tree1):
            if not tree1:
                return False
            if tree1.val == subRoot.val:
                ans = dfs2(tree1, subRoot)
                if ans: return ans
            left = dfs1(tree1.left)
            right = dfs1(tree1.right)
            return left or right

        def dfs2(tree1, tree2):
            if not tree1 and not tree2:
                return True
            if not tree1 or not tree2:
                return False
            if tree1.val != tree2.val:
                return False
            
            left = dfs2(tree1.left, tree2.left)
            right = dfs2(tree1.right, tree2.right)
            return left and right
        
        return dfs1(root)

class Solution:
    # 代码逻辑同 104. 二叉树的最大深度
    def getHeight(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        left_h = self.getHeight(root.left)
        right_h = self.getHeight(root.right)
        return max(left_h, right_h) + 1

    # 100. 相同的树
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p is None or q is None:
            return p is q  # 必须都是 None
        return p.val == q.val and \
            self.isSameTree(p.left, q.left) and \
            self.isSameTree(p.right, q.right)

    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        hs = self.getHeight(subRoot)

        # 返回 node 的高度，以及是否找到了 subRoot
        def dfs(node: Optional[TreeNode]) -> (int, bool):
            if node is None:
                return 0, False
            left_h, left_found = dfs(node.left)
            right_h, right_found = dfs(node.right)
            if left_found or right_found:
                return 0, True
            node_h = max(left_h, right_h) + 1
            return node_h, node_h == hs and self.isSameTree(node, subRoot)
        return dfs(root)[1]