判断一棵树是否为另一棵树的子树的算法

Question

我正在阅读《破解面试官》一书，对以下问题的解决方案有疑问：你有两个非常大的二叉树：T1具有数百万个节点，而T2只有数百个节点。创建一个算法来确定T2是否是T1的子树。

它建议的简单解决方案是创建一个表示中序遍历和先序遍历的字符串，并检查T2的先序/中序遍历是否是T1的先序/中序遍历的子串。

我想知道为什么需要比较两种遍历方式？为什么要比较这两种遍历方式，而不是例如中序遍历和后序遍历？主要的问题是，只使用其中一种遍历方式是否足够？比如只使用中序遍历或先序遍历？

- mkd156

---

首先让我们澄清一下你所说的“子树”的含义。标准的图理论含义是指“通过从一棵树中删除零个或多个顶点和边而形成的子图，它本身也是一棵树”——但是另外一种常用的含义是“删除一条边，剩下2个连通分量，两者都是子树”。前一个定义包括了后者不包括的一些树。 - j_random_hacker

有趣的是，您提供的算法在某些合理的“子树”定义下将无法工作：作为一名数学家，我会将2<-1->3称为4<-2<-1->3->5的子树。但第一个的前序遍历不是第二个的子字符串。 - Joel

当你说“二叉树”时，我们可以假设它们是“二叉搜索树”（即，父节点小于其任何两个子节点）吗？此外，每棵树上的节点值是否唯一？ - Matthieu M.

Answer 1

一次遍历是不够的。考虑图1->2->3和2<-1->3。如果你从节点1开始遍历，你会按顺序遇到节点1、2、3。如果你只是创建一个字符串来显示前序，这两个顺序会给出相同的结果：1,2,3 另一方面，如果你使用后序，那么这两个顺序将给出不同的结果：3,2,1 和 2,3,1 我敢打赌，无论哪种顺序，你都可以找到两个不同的树，它们的结果相同。

因此，对于你想查看的任何其他节点对，你需要回答自己的问题是：是否存在一棵树，使得两种遍历都给出相同的顺序？我会把这个问题留给你思考，稍后再来看看你是否搞清楚了。

- Joel

Answer 2

我认为使用哨兵表示空节点的先序遍历已经足够了。我们可以使用这种方法来序列化/反序列化二叉树。也就是说，二叉树与其先序+哨兵表示之间存在一对一的映射关系。

在获取小树和大树的字符串后，我们可以使用KMP算法进行字符串匹配。

我知道有人说我们必须同时使用先序和中序（或后序和中序）。但他们大多数只是跟随别人的说法，而不是独立思考。

- e230217