为什么中序遍历和先序遍历在创建判断T2是否为T1子树的算法中很有用？

Question

9

我正在查看一本面试书，其中有一个问题是：

您有两个非常大的二叉树：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提出了一个很好的观点。假设两个树都没有重复节点。

- But I'm Not A Wrapper Class

假设你从《破解编程面试》这本书中得到了这个问题，作者实际上提到树可以有重复的节点，并且甚至展示了一个例子。她解决的方法是同时打印叶子节点的空值。 - Cheng

3个回答

1

这里有一个反例来说明这种方法的问题。

考虑树 T1:

  B
 / \
A   D
   / \
  C   E
       \
        F

而子树 T2：

  D
 / \
C   E

相关的遍历方式如下:

尽管 DCE 在 BADCEF 中，CDE 在 ABCDEF 中，但是 T2 实际上并不是 T1 的子树。作者对子树的定义可能不同，或者这只是一个错误。

- Daniel Imms

为什么我们不关心后序遍历呢？此外，你的 BADCEF 计数器示例没有意义...也许我没有看到什么。 - But I'm Not A Wrapper Class

1

子树的定义是什么？ - gen

1

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

现在请注意，先序遍历字符串和中序遍历字符串可以唯一地识别二叉树。

证明的草图：

假设T是一个树。

1. 先序遍历字符串(T)的第一个对象是根。 2. 在inorder-traversal-string(T)中找到它——左侧所有元素是你的左子树L，让我们称这个子字符串为inorder-traversal-string(L)。右侧的所有元素是你的右子树R。 3. 现在，让我们专注于左子树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 唯一描述。

- Łukasz Kidziński

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bartosz Marcinkowski · Accepted Answer

我认为这不是真的。请考虑以下内容：

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 的子树。