algorithm - 使用前序和中序字符串确定二叉树是否是另一棵二叉树的子树

Question

我想找出二叉树 T2 是否是二叉树 T1 的子树。我读到，可以使用先序遍历和中序遍历为 T2 和 T1 构建字符串表示，如果 T2 字符串是 T1 字符串的子字符串，则 T2 是 T1 的子树。

我对这个方法有点迷惑，不确定它的正确性。

来自 wiki:“树 T 的子树是由 T 中的一个节点及其在 T 中的所有后代组成的树。”

在下面的例子中:

T2:
  1
 / \
2   3

T1:
  1
 / \
2   3
     \
      4

如果我们为 T2 和 T1 构建字符串:

预购 T2:“1,2,3”
预购 T1:“1,2,3,4”
顺序 T2: "2,1,3"
顺序 T1:“2,1,3,4”

T2的字符串是T1的子串，所以使用上面描述的子串匹配方法，我们应该得出T2是T1的子树。

但是，根据定义，T2 不应该是 T1 的子树，因为它没有 T1 根节点的所有后代。

有相关讨论here , 这似乎得出结论该方法是正确的。

我是不是漏掉了什么？

Answer 1

非常有趣的问题。你似乎是正确的。我想你提到的问题是由于 math (graph theory) 中子树的不同定义引起的。和计算机科学。在图论中，T2 是 T1 的真子树。