为什么有序遍历和预遍历遍历对于创建确定T2是否为T1的子树的算法很有用 [英] Why is inorder and preorder traversal useful for creating an algorithm to decide if T2 is a subtree of T1

问题描述

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

I'm looking at an interview book and the question is:

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

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.

作者提到这是一种可能的解决方案：

The authors mentions this as a possible solution:

这里的问题指定 T1 具有数百万个
节点-这意味着我们应注意要使用多少空间。
例如， T1 拥有1000万个节点-这意味着仅
数据就约 40 mb 。 我们可以创建一个表示
有序遍历和预定遍历的字符串。如果 T2 的预订遍历是 T1 的预订遍历的
子字符串，而 T2 的顺序遍历是 T1 的顺序遍历的
子字符串，然后是 T2 是 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.

I对于这些原因是否成立，我不太确定背后的逻辑：

I'm not quite sure the logic behind as to why if these are true:

• T2-preorder-traversal- string 是 T1-preorder-traversal-string


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

• T2-preorder-traversal-string is a substring of T1-preorder-traversal-string
• T2-inorder-traversal-string is a substring of T1-inorder-traversal-string

T2 必须是 T1 。我可以对此逻辑进行解释吗？

That T2 must be a substring (although I assume the author means subtree) of T1. Can I get an explanation to this logic?

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

EDIT: User BartoszMarcinkowski brings up a good point. Assume both trees have no duplicate nodes.

推荐答案

我认为这是不正确的。考虑：

I think it is not true. Consider:

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

123 is substring of 0123103, 213 is substring of 0310213, but T2 is not subtree of T1.

这篇关于为什么有序遍历和预遍历遍历对于创建确定T2是否为T1的子树的算法很有用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！