我正在看一本采访书，问题是：
你有两个非常大的二叉树：T1，拥有数百万个节点，并且T2，有数百个节点。创建一个算法来决定是否T2是一个
的子树T1.
作者提到这是一个可能的解决方案：
请注意，这里的问题指定T1有数百万
节点——这意味着我们应该注意我们使用的空间量。
比方说，T1有 1000 万个节点——这意味着
数据本身就是关于40 mb. 我们可以创建一个字符串来表示
中序和前序遍历. If T2的前序遍历是
的子串T1的前序遍历，以及T2的中序遍历是
的子串T1的中序遍历，则T2是一个子串T1.
我不太确定为什么这些是真的背后的逻辑：
-
T2-preorder-traversal-string是一个子串T1-preorder-traversal-string
-
T2-inorder-traversal-string是一个子串T1-inorder-traversal-string
That T2必须是一个子串（尽管我假设作者指的是子树）T1。我能得到这个逻辑的解释吗？
EDIT: User 巴托斯·马辛科夫斯基提出了一个很好的观点。假设两棵树都没有重复的节点。
我认为这不是真的。考虑：
T2:
2
/ \
1 3
inorder 123 preorder 213
and
T1:
0
/ \
3 3
/ \
1 1
/ \
0 2
inorder 0123103 preorder 0310213
123是子串0123103, 213是子串0310213，但 T2 不是 T1 的子树。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
