为什么无序遍历和前置遍历对于创建一个算法来确定T2是否是T1的子树很有用？

Question

我正在看一本采访书，问题是：

您有两个非常大的二叉树：T1 (数百万节点)和T2 (数百个节点)。创建一个算法来确定T2是否是T1的子树。

作者提到这是一种可能的解决办法：

请注意，这里的问题指定T1有数百万个节点--这意味着我们应该小心使用多少空间。例如，假设T1有1000万个节点--这意味着仅数据就是关于40 mb的。我们可以创建一个字符串，表示无序和前置遍历。如果T2的序遍历是T1序遍历的子串，T2的序遍历是T1序遍历的子串，则T2是T1的子串。

我不太清楚为什么这些都是真的：

• T2-preorder-traversal-string是T1-preorder-traversal-string的子字符串
• T2-inorder-traversal-string是T1-inorder-traversal-string的子字符串

T2必须是T1的子字符串(尽管我假设作者是子树)。我能解释一下这个逻辑吗？

编辑：用户BartoszMarcinkowski提出了一个很好的观点。假设两棵树都没有重复的节点。

Answer 1

我认为这不是真的。考虑：

T2:

  2
 / \
1   3

inorder 123 preorder 213

和

T1:

      0
     / \
    3   3
   / \ 
  1   1
 / \ 
0   2


inorder 0123103 preorder 0310213

123是0123103的子字符串，213是0310213的子字符串，但T2不是T1的子树。

Answer 2

以下是该方法的反例。

以树T1为例

  B
 / \
A   D
   / \
  C   E
       \
        F

和子树T2

  D
 / \
C   E

相关的横断面是：

• T1预订货：BADCEF
• T2预订货：DCE
• T1 order：ABCDEF
• T2 order：CDE

DCE在BADCEF中，CDE在ABCDEF中，T2实际上不是T1的子树。作者对子树的定义一定是不同的，否则这只是一个错误。

相关问题：Determine if a binary tree is subtree of another binary tree using pre-order and in-order strings

Answer 3

重要的假设是树有唯一的键。

现在，请注意，preorder-traversal-string和inorder-traversal-string唯一地标识了二叉树。

证明的样条：

让T成为一棵树。

• preorder-traversal-string(T)中的第一个对象是根。
• 在inorder-traversal-string(T)中找到它--该元素左侧的所有内容都是您的左子树L，让我们调用这个子字符串inorder-traversal-string(L)。右边的所有东西都是您的右子树R。

现在，让我们关注左侧子树L。

• 显然，在两个字符串中，所有子树都是分开的(它们不混合)。它们被表示为连续的对象。唯一的问题是，我们事先不知道preorder-traversal-string(L)在preorder-traversal-string(T)中的结尾位置。
• 注意，字符串inorder-traversal-string(L)和preorder-traversal-string(L)具有相同的长度。这里作为切割的地方。
• 现在您有了一个子树，它被描述为子字符串inorder-traversal-string(L)和preorder-traversal-string(L)，所以您可以重复这个过程直到结束。

按照这些步骤(效率低下，但这只是为了证明)，您将唯一地构建树。

因此，T1的所有子树都由相应的inorder-traversal-string和preorder-traversal-string唯一描述。