本文共 1902 字，大约阅读时间需要 6 分钟。

本系列文章为《剑指Offer》刷题笔记。

刷题平台：

这类题目与字符串匹配有些神似，求解过程大致分为两步：

• 先将根节点匹配；
• 根节点匹配后，对子树进行匹配。

最终代码如下：

代码中主要涉及 主函数checkSubTree和 dfs 函数 两个部分。与以上思路对应，主函数对应根节点的匹配，dfs 函数对应匹配其他节点。

1.dfs 函数

dfs 函数将注意力集中在了根节点已经匹配的情况。当从根节点同时开始向下遍历时，我们进行以下判断：

• 如果 A 和 B 同时遍历到了 null，说明匹配成功，返回 True（case 1 红色虚线框）；
• 如果 A 或 B 提前遍历到了 null，一棵树匹配完了，另一棵却没有，说明子树的结构是不同的，则匹配失败，返回 False（case 2 红色虚线框）。

以上是“基本情况”，在到达基本情况之前，我们需要判断根节点的值、左子树（调用递归）和右子树（调用递归）是否匹配。

于是就有了代码中的 dfs 函数形式：

2.主函数checkSubTree

现在将视野放远来看，主函数则解决了如何确定 A 的哪个节点是 B 的根节点。

如果 A 的当前节点值与 B 的根节点值相同，我们调用 dfs 函数判断子树是否也相同；如果不同，我们就递归调用主函数来寻找 A 的哪个节点与 B 的根节点匹配。

所以，主函数会写成这样：

【本题解法】 对于本题来讲，与前面的例题很像，不同的是 B 属于 A 的一部分也可以，没必要一直匹配到叶子节点。因此只需对 check 函树的基本条件进行修改即可。

< Leetcode >

class Solution:    def check(self, s, t): # 这里 t 可能为空        if not t:            return True        if not s:            return False                return s.val == t.val and self.check(s.left, t.left) and self.check(s.right, t.right)    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:        if not A or not B: return False        return self.check(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)

链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/pi-pei-lei-er-cha-shu-ti-mu-zong-jie-by-z1m/

< 牛客 >

# -*- coding:utf-8 -*-# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    def HasSubtree(self, pRoot1, pRoot2):        if not pRoot1 or not pRoot2:            return False        return self.isSubStructure(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)            def isSubStructure(self, A, B):        if not B:            return True        if not A:            return False        return A.val == B.val and self.isSubStructure(A.left, B.left) and self.isSubStructure(A.right, B.right)

https://www.cnblogs.com/ansang/p/11938132.html