y****n
发帖数: 15 | 1 题目描述 Q4.8：
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.
书中的解法一：
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 subtree of T1.
我感觉这个方法可能有问题。虽然通过preorder和inorder遍历，可以唯一的定义一棵
树。但是如果T2是T1的子树，遍历字符串S2是S1的子串，那么S2可能对应到S1的不同位
置。举例来说，下面两棵树就满足S2是S1的子串，但T2不是T1的子树。
请众位高手帮忙检查一下，是我的结果有问题，还是书中有错误，多谢！
2 2
/ \ / \
1 2 1 3
/ / \
3 4 3
/ \
5 1
Preorder: S1=21324513 S2=213
Inorder: S1=31254123 S2=123 | m*******l
发帖数: 12782 | 2 书错了
of
and
【在 y****n 的大作中提到】
: 题目描述 Q4.8：
: 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.
: 书中的解法一：
: 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 subtree of T1.
: 我感觉这个方法可能有问题。虽然通过preorder和inorder遍历，可以唯一的定义一棵
: 树。但是如果T2是T1的子树，遍历字符串S2是S1的子串，那么S2可能对应到S1的不同位
|
|
