美国学校很强大呀 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

美国学校很强大呀 (转载)

美国学校很强大呀 (转载)# Joke - 肚皮舞运动

c*y2012-11-01 07:11

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

x*o2012-11-01 07:11

2 楼

【以下文字转载自 WashingtonDC 讨论区】
发信人: poker72266 (poker), 信区: WashingtonDC
标题: 美国学校很强大呀
发信站: BBS 未名空间站 (Thu Nov 1 10:33:01 2012, 美东)
昨天带儿子去要糖
他坚持每家只拿一块
人要他多拿几块
他说了很多次＂NO THANKS＂
其实我们GREEDY父母以前教他要多拿的
还有不少其他事儿让我惭愧
比如HIKING时扔空BOTTLE
向车窗外扔桃核
都被儿子指正
还有一次在GIANT买的西瓜没被算钱我很高兴
儿子说那是CHEATING
美国学校很强大呀
所以教出来的美国人都很傻

l*b2012-11-01 07:11

3 楼

记得这题大家说有点bug
brutal force好像复杂度很高吧

E*A2012-11-01 07:11

4 楼

坑王风范

c*y2012-11-01 07:11

5 楼

brutal force复杂度是比较高，但是如果有duplicate的话，只能用brutal force吧。
我只是不理解为什么CC150和我贴的论坛上说只用InOrder和PreOrder就可以了。上面那
个反例说明只用InOrder和PreOrder不够的。另外一个问题是InOrder,PreOrder和
PostOrder是不是就可以了呢（对于没有duplicate的元素）？

s*a2012-11-01 07:11

6 楼

挺好的呀，小朋友纯洁的心灵。

【在 x****o 的大作中提到】

: 【以下文字转载自 WashingtonDC 讨论区】
: 发信人: poker72266 (poker), 信区: WashingtonDC
: 标题: 美国学校很强大呀
: 发信站: BBS 未名空间站 (Thu Nov 1 10:33:01 2012, 美东)
: 昨天带儿子去要糖
: 他坚持每家只拿一块
: 人要他多拿几块
: 他说了很多次＂NO THANKS＂
: 其实我们GREEDY父母以前教他要多拿的
: 还有不少其他事儿让我惭愧

e*e2012-11-01 07:11

7 楼

我觉得你的反例已经说明只用InOrder和PreOrder是不行的。我也给出一个反例说明即
使有PostOrder还是不行。
T1:
1
/
2
T2:
1

【在 c**y 的大作中提到】

: brutal force复杂度是比较高，但是如果有duplicate的话，只能用brutal force吧。
: 我只是不理解为什么CC150和我贴的论坛上说只用InOrder和PreOrder就可以了。上面那
: 个反例说明只用InOrder和PreOrder不够的。另外一个问题是InOrder,PreOrder和
: PostOrder是不是就可以了呢（对于没有duplicate的元素）？

s*l2012-11-01 07:11

8 楼

这孩子有出息，至少自控能力很强

B*t2012-11-01 07:11

9 楼

是你自己弄错了吧。。
用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*y2012-11-01 07:11

10 楼

多谢楼上指出PreOrder和InOrder算法的关键，我确实忽略了关于特殊字符的使用。这
个论坛上的人已经给出了这样的算法。具体参见Himanshu给的solution
http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-
我另外有两个问题
1. PostOrder和InOrder+特殊字符的方法是不是同样可行呢？
2. PreOrder，InOrder和PostOrder不加特殊字符的方法可以不可以呢？

c*t2012-11-01 07:11

11 楼

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*y2012-11-01 07:11

12 楼

多谢回复，还是有两个问题不明白，能否详细指教一下。

这个用特殊字符的方法一定要比较Both PreOrder（或者PostOrder）和InOrder的序列
吗？如果是的话，原因是什么呢？
啥是ls迪迪贴呀？另外问题2可能我没有表述清楚。我的意思是比较三个序列（分别由
InOrder，PreOrder和PostOrder Traversal的方法生成，但是不加任何特殊字符）。这
样三个序列不能唯一的确定一个Binary Tree吗？

【在 c********t 的大作中提到】

: 1. PostOrder和InOrder+特殊字符的方法是不是同样可行呢？
: 是
: 2. PreOrder，InOrder和PostOrder不加特殊字符的方法可以不可以呢？
: 不可以，见ls迪迪贴

c*t2012-11-01 07:11

13 楼

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*12012-11-01 07:11

14 楼

我也觉得此题很莫名，如果null用特殊符号算的话，单用preorder就行了，我举不出单
用preorder的反例~似乎serialize 和 deserialize 也只用preorder~

c*y2012-11-01 07:11

15 楼

多谢回复。迪迪的帖子证明了即便inorder，preorder，和postorder都用也是不行的。
关于如果允许使用特殊字符的话，好像只要一个就可以了，either inorder, preorder
或者postorder都可以。通过使用特殊字符，一个binary tree的信息可以被一个序列完
全复制和恢复。因此只要一个序列就可以了。例如
2
/ \
1 3
Inorder: (1)2(3)
Preorder: 21()3()
Postorder: ()1()32
多谢各位

y*g2012-11-01 07:11

16 楼

你所谓的特殊字符是什么？

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*y2012-11-01 07:11

17 楼

特殊字符就是()
以下是个inorder的例子
printf("(");
inrodervisit(p_node->p_leftchild);
printf(")");
printf(p_node->value);
printf("(");
inrodervisit(p_node->p_rightchild);
printf(")");
这样每次访问一个新的subtree，总是会打印一个（）surrounding这个subtree的序列
。