algorithm - 为什么中序和先序遍历对于创建算法来确定 T2 是否是 T1 的子树很有用

Question

我正在看一本面试书，问题是:

You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.

作者提到这是一个可能的解决方案:

Note that the problem here specifies that T1 has millions of nodes—this means that we should be careful of how much space we use. Let’s say, for example, T1 has 10 million nodes—this means that the data alone is about 40 mb. We could create a string representing the inorder and preorder traversals. If T2’s preorder traversal is a substring of T1’s preorder traversal, and T2’s inorder traversal is a substring of T1’s inorder traversal, then T2 is a substring of 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的子树.