检查一棵二叉树是否为另一棵二叉树的子树

引言

二叉树是计算机科学中使用的基本数据结构，广泛应用于各种算法和应用程序中。二叉树中遇到的一个常见问题是确定一棵树是否是另一棵树的子树。该问题在软件开发、数据库系统和人工智能等领域具有实际应用。

理解二叉树和子树

在深入探讨这个问题之前，让我们先澄清一些基本概念。二叉树是一种层次结构的数据结构，由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树的子树是通过从原始树中选择一个节点（及其所有后代）并将其视为新树的根而形成的树。

例如，我们给定两棵二叉树，假设为树 A 和树 B，我们需要确定树 B 是否是树 A 的子树。一棵树的子树是由原始树中的一个节点及其所有后代组成的树。因此，要检查树 B 是否是树 A 的子树，我们需要验证树 A 中是否存在一个子树与树 B 完全相同。

方法

为了确定一棵二叉树是否是另一棵二叉树的子树，我们需要设计一种算法，该算法在高效遍历两棵树的同时检查每个节点的相等性。以下是实现此目的的循序渐进方法：

• 树遍历

我们将使用递归方法遍历主树和潜在子树。深度优先搜索 (DFS) 遍历是树遍历算法的常见选择。在 DFS 中，我们在回溯之前尽可能地沿着每个分支进行探索。我们将对主树执行 DFS，并在每个节点处检查它是否与子树的根匹配。

• 比较

在主树的每个节点处，如果我们发现该节点与子树的根匹配，我们将开始比较子树与从当前节点开始的主树部分。此比较也将递归进行，检查两棵树中相应的节点是否匹配。

• 基本情况

我们需要为我们的递归函数定义基本情况。这些包括子树为空（这 Trivially 意味着它是一个子树），或者当我们到达两棵树的叶节点并且它们匹配时的场景。

• 递归

对主树和潜在子树的左右子树递归调用比较函数。

• 终止条件

当潜在子树中的所有节点都用尽时，或者当我们在两棵树中的相应节点之间发现不匹配时，递归应该终止。

实施

输出

说明

• 该程序定义了一个 TreeNode 结构，它表示二叉树中的一个节点。每个节点都有一个整数值 val，以及指向其 left 和 right 子节点的指针。
• 这个结构有一个构造函数，用于用给定值初始化节点，并将其子节点指针设置为
• 在结构定义之后，程序定义了一个辅助函数 isIdentical，它接受两个二叉树节点 s 和 t 并检查它们是否相同。它递归地比较节点的值及其左右子树以确定它们是否相同。
• 主函数 isSubtree 负责确定树 t 是否是树 s 的子树。
• 它遍历树 s，并在每个节点处，使用 isIdentical 检查当前子树是否与树 t 相同。如果它找到一个相同的子树，或者如果它在当前节点中没有找到相同的子树但在其左子树或右子树中找到一个，它返回 true，表示 t 是 s 的子树。
• 在主函数中，演示了一个示例用法。创建并初始化了两棵二叉树 s 和 t 的值。
• 然后，使用 s 和 t 调用 isSubtree 函数。如果 t 是 s 的子树，它打印“是的，t 是 s 的子树。”，否则，它打印“不，t 不是 s 的子树。”

复杂度分析

令 m 为较大树中的节点数，n 为较小树中的节点数。

• 时间复杂度： 在最坏情况下，较大树的每个节点将被访问一次，以检查它是否与较小树的根匹配。此外，在每次匹配时，我们将遍历子树以检查相等性。因此，时间复杂度为 O(m.n)，其中 m 是较大树中的节点数，n 是较小树中的节点数。
• 空间复杂度： 空间复杂度由递归栈决定。在最坏情况下，递归深度可以是 O(m)（其中 m 是较大树中的节点数），这对应于较大树的高度。

结论

总之，使用递归深度优先搜索方法可以有效地解决确定一个二叉树是否是另一个二叉树的子树的问题。通过遍历两棵树并比较它们的节点，我们可以确定子树的相等性。所提供的实现展示了一个简单而有效的解决方案。凭借 O(m.n) 的时间复杂度和由递归栈决定的空间复杂度，该方法为各种应用中的子树识别提供了实用的解决方案。