c**y
发帖数: 172 | 1 问题简单概述：Binary Tree T1（大）和T2（小），判断T2是不是T1的substree。
CC150给的解法是对于每一个Tree，用InOrder和PreOrder的方法生成两个序列，然后判
断T2的两个序列是不是T1两个序列的substring。CC150还有brutal force的解法（这里
就不讨论了）。
我的问题是
1.这个序列比较的解法要求T1和T2不能有duplicate元素？这个应该是确定的，参见
http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-
2.为什么不比较PostOrder生成的序列呢？下面是一个反例（如果只用PreOrder和
InOrder
，返回True，但是实际应该是False）
T1:
1
/ \
2 3
\
4
T2:
1
/ \
2 3
T1:
InOrder: 2134
PreOrder: 1234
T2:
InOrder: 213
PreOrder: 123
如果只用InOrder和PreOrder，T2是T1的subtree。但是如果考虑PostOrder的话，就不
是了。
T1
PostOrder：2431
T2
PostOrder：231 |
l*******b
发帖数: 2586 | 2 记得这题大家说有点bug
brutal force好像复杂度很高吧 |
c**y
发帖数: 172 | 3 brutal force复杂度是比较高，但是如果有duplicate的话，只能用brutal force吧。
我只是不理解为什么CC150和我贴的论坛上说只用InOrder和PreOrder就可以了。上面那
个反例说明只用InOrder和PreOrder不够的。另外一个问题是InOrder,PreOrder和
PostOrder是不是就可以了呢（对于没有duplicate的元素）？ |
e****e
发帖数: 418 | 4 我觉得你的反例已经说明只用InOrder和PreOrder是不行的。我也给出一个反例说明即
使有PostOrder还是不行。
T1:
1
/
2
T2:
1
【在 c**y 的大作中提到】
: brutal force复杂度是比较高，但是如果有duplicate的话，只能用brutal force吧。
: 我只是不理解为什么CC150和我贴的论坛上说只用InOrder和PreOrder就可以了。上面那
: 个反例说明只用InOrder和PreOrder不够的。另外一个问题是InOrder,PreOrder和
: PostOrder是不是就可以了呢（对于没有duplicate的元素）？
|
B********t
发帖数: 147 | 5 是你自己弄错了吧。。
用preorder inorder的方法，T2就不是T1的subtree. preorder inorder的这种方法是
需要在node之间加一些special character的，以便知道哪些左 右子树为NULL.
T1：inorder: 0201034
T2: inorder: 0201030
【在 c**y 的大作中提到】
: 问题简单概述：Binary Tree T1（大）和T2（小），判断T2是不是T1的substree。
: CC150给的解法是对于每一个Tree，用InOrder和PreOrder的方法生成两个序列，然后判
: 断T2的两个序列是不是T1两个序列的substring。CC150还有brutal force的解法（这里
: 就不讨论了）。
: 我的问题是
: 1.这个序列比较的解法要求T1和T2不能有duplicate元素？这个应该是确定的，参见
: http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-
: 2.为什么不比较PostOrder生成的序列呢？下面是一个反例（如果只用PreOrder和
: InOrder
: ，返回True，但是实际应该是False）
|
c**y
发帖数: 172 | 6 多谢楼上指出PreOrder和InOrder算法的关键，我确实忽略了关于特殊字符的使用。这
个论坛上的人已经给出了这样的算法。具体参见Himanshu给的solution
http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-
我另外有两个问题
1. PostOrder和InOrder+特殊字符的方法是不是同样可行呢？
2. PreOrder，InOrder和PostOrder不加特殊字符的方法可以不可以呢？ |
c********t
发帖数: 5706 | 7 1. PostOrder和InOrder+特殊字符的方法是不是同样可行呢？
是
2. PreOrder，InOrder和PostOrder不加特殊字符的方法可以不可以呢？
不可以，见ls迪迪贴
【在 c**y 的大作中提到】
: 多谢楼上指出PreOrder和InOrder算法的关键，我确实忽略了关于特殊字符的使用。这
: 个论坛上的人已经给出了这样的算法。具体参见Himanshu给的solution
: http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-
: 我另外有两个问题
: 1. PostOrder和InOrder+特殊字符的方法是不是同样可行呢？
: 2. PreOrder，InOrder和PostOrder不加特殊字符的方法可以不可以呢？
|
c**y
发帖数: 172 | 8 多谢回复，还是有两个问题不明白，能否详细指教一下。
这个用特殊字符的方法一定要比较Both PreOrder（或者PostOrder）和InOrder的序列
吗？如果是的话，原因是什么呢？
啥是ls迪迪贴呀？另外问题2可能我没有表述清楚。我的意思是比较三个序列（分别由
InOrder，PreOrder和PostOrder Traversal的方法生成，但是不加任何特殊字符）。这
样三个序列不能唯一的确定一个Binary Tree吗？
【在 c********t 的大作中提到】
: 1. PostOrder和InOrder+特殊字符的方法是不是同样可行呢？
: 是
: 2. PreOrder，InOrder和PostOrder不加特殊字符的方法可以不可以呢？
: 不可以，见ls迪迪贴
|
c********t
发帖数: 5706 | 9 1. 我感觉两两组合都可以 Pre+post也应该可以，看看有没有人能给出反例
2. 楼上迪迪说的例子,就是反例啊
tree 1
1
/
2
tree 2
1
【在 c**y 的大作中提到】
: 多谢回复，还是有两个问题不明白，能否详细指教一下。
:
: 这个用特殊字符的方法一定要比较Both PreOrder（或者PostOrder）和InOrder的序列
: 吗？如果是的话，原因是什么呢？
: 啥是ls迪迪贴呀？另外问题2可能我没有表述清楚。我的意思是比较三个序列（分别由
: InOrder，PreOrder和PostOrder Traversal的方法生成，但是不加任何特殊字符）。这
: 样三个序列不能唯一的确定一个Binary Tree吗？
|
s*****1
发帖数: 134 | 10 我也觉得此题很莫名，如果null用特殊符号算的话，单用preorder就行了，我举不出单
用preorder的反例~似乎serialize 和 deserialize 也只用preorder~ |
c**y
发帖数: 172 | 11 多谢回复。迪迪的帖子证明了即便inorder，preorder，和postorder都用也是不行的。
关于如果允许使用特殊字符的话，好像只要一个就可以了，either inorder, preorder
或者postorder都可以。通过使用特殊字符，一个binary tree的信息可以被一个序列完
全复制和恢复。因此只要一个序列就可以了。例如
2
/ \
1 3
Inorder: (1)2(3)
Preorder: 21()3()
Postorder: ()1()32
多谢各位 |
y*******g
发帖数: 6599 | 12 你所谓的特殊字符是什么？
preorder
【在 c**y 的大作中提到】
: 多谢回复。迪迪的帖子证明了即便inorder，preorder，和postorder都用也是不行的。
: 关于如果允许使用特殊字符的话，好像只要一个就可以了，either inorder, preorder
: 或者postorder都可以。通过使用特殊字符，一个binary tree的信息可以被一个序列完
: 全复制和恢复。因此只要一个序列就可以了。例如
: 2
: / \
: 1 3
: Inorder: (1)2(3)
: Preorder: 21()3()
: Postorder: ()1()32
|
c**y
发帖数: 172 | 13 特殊字符就是()
以下是个inorder的例子
printf("(");
inrodervisit(p_node->p_leftchild);
printf(")");
printf(p_node->value);
printf("(");
inrodervisit(p_node->p_rightchild);
printf(")");
这样每次访问一个新的subtree，总是会打印一个（）surrounding这个subtree的序列
。 |
