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

问题描述

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

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

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

The authors mentions this as a possible solution:

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的子树的算法很有用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！