为什么序和preorder traversel创建的算法，如果T2决定有用的是T1的子树 [英] Why is inorder and preorder traversel 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 拥有10万个节点，这意味着   单独的数据是关于 40 MB 。 我们可以创建一个字符串，再presenting的   序和preorder遍历。如果 T2 的preorder遍历是   的子T1 的preorder遍历和 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'm not quite sure the logic behind as to why if these are true:

• T2- preorder遍历字符串是一个子 T1- preorder遍历字符串
• T2-序遍历字符串是 T1-序遍历字符串

• 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.

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