1.题目基本信息

1.1.题目描述

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

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

1.2.题目地址

https://leetcode.cn/problems/subtree-of-another-tree/description/

2.解题方法

2.1.解题思路

深度优先搜索+先序遍历+KMP匹配

时间复杂度：O(n)

2.2.解题步骤

第一步，构建深搜函数，获取先序遍历序列。包括空节点在内对树进行深度优先搜索，获取先序遍历序列order（注意node不可为空节点）

第二步，使用KMP匹配算法，计算subRoot的深搜序列是否在root的深搜序列中

3.解题代码

python代码

# 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:
        # 思路：深度优先搜索+先序遍历+KMP匹配
        lNull = - 10 ** 5
        rNull = 10 ** 5
        # 第一步，构建深搜函数，获取先序遍历序列。包括空节点在内对树进行深度优先搜索，获取先序遍历序列order（注意node不可为空节点）
        def dfs(node:TreeNode) -> list[int]:
            if node.left is not None:
                lorder = dfs(node.left)
            else:
                lorder = [lNull]
            if node.right is not None:
                rorder = dfs(node.right)
            else:
                rorder = [rNull]
            return [node.val] + lorder + rorder
        # 第二步，使用KMP匹配算法，计算subRoot的深搜序列是否在root的深搜序列中
        rootOrder = dfs(root)
        subOrder = dfs(subRoot)
        # print(rootOrder)
        # print(subOrder)
        n1 = len(subOrder)
        pmArr = [0] * n1
        preLen = 0
        i = 1
        while i < n1:
            if subOrder[i] == subOrder[preLen]:
                i += 1
                preLen += 1
                pmArr[i] += 1
            else:
                if preLen == 0:
                    i += 1
                else:
                    preLen = pmArr[preLen - 1]
        n2 = len(rootOrder)
        i, j = 0, 0
        while i < n2:
            if rootOrder[i] == subOrder[j]:
                i += 1
                j += 1
            else:
                if j == 0:
                    i += 1
                else:
                    j = pmArr[j - 1]
            if j == n1:
                return True
        return False

4.执行结果