为什么inorder和preorder遍历对于创建算法以确定T2是否是T1的子树非常有用

Question

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

您有两个非常大的二叉树:T1具有数百万个节点,并且 T2具有数百个节点.创建一个算法来确定是否T2是子树T1.

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

请注意,此处的问题指定T1有数百万个节点 - 这意味着我们应该注意我们使用了多少空间.例如,假设T1有1000万个节点 - 这意味着仅有数据40 mb.我们可以创建一个表示inorder和preorder遍历的字符串.如果T2preorder遍历是's preorder遍历的子字符串T1,并且T2inorder遍历是遍历遍历的子字符串T1,那么它T2是一个子字符串T1.

我不太清楚为什么如果这些是真的背后的逻辑:

• T2-preorder-traversal-string 是一个子串 T1-preorder-traversal-string
• T2-inorder-traversal-string 是一个子串 T1-inorder-traversal-string

那T2必须是子串(虽然我假设作者的意思是子树)T1.我能解释一下这个逻辑吗？

编辑:用户BartoszMarcinkowski提出了一个好点.假设两个树都没有重复的节点.

Answer 1

这是该方法的反例。

考虑树T1：

  B
 / \
A   D
   / \
  C   E
       \
        F

和子树T2：

  D
 / \
C   E

相关的遍历是：

• T1预购：BADCEF
• T2预购：DCE
• T1为了：ABCDEF
• T2为了：CDE

虽然DCEis inBADCEF和CDEis in ABCDEF，T2实际上不是 的子树T1。作者对子树的定义一定是不同的，或者只是一个错误。

相关问题：使用前序和中序字符串确定一棵二叉树是否是另一棵二叉树的子树