请较一道面世题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

请较一道面世题

请较一道面世题# JobHunting - 待字闺中

x*u2015-06-29 07:06

1 楼

就是两个binary tree, 一大, 一小.
check 小树是否是大树的sub tree.
recursive的方法不谈了, 很清晰的解法.
另一种是把binary tree 存成 string, 然后用kmp 来check substring.
cracking code 150, 还有 geeksforgeeks 上面都是需要用preorder 和inorder
traversal 两种方法. 说是只有这样才能unique identify the tree.
个人觉得preorder traversal 加上 '#' mark null node就足够了. 没必要再用
inorder traversal了. 因为BT serialize/deserialze, preorder + sentinel 就够了.
请牛人指教.谢谢.

b*12015-06-29 07:06

2 楼

貌似你说的这种null用#来表示的方法就是CC答案上说的诶，应该是make sense的

s*l2015-06-29 07:06

3 楼

如果有node的内容就是'#' 这样的Dummy node 就不好用了把~

了.

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

: 就是两个binary tree, 一大, 一小.
: check 小树是否是大树的sub tree.
: recursive的方法不谈了, 很清晰的解法.
: 另一种是把binary tree 存成 string, 然后用kmp 来check substring.
: cracking code 150, 还有 geeksforgeeks 上面都是需要用preorder 和inorder
: traversal 两种方法. 说是只有这样才能unique identify the tree.
: 个人觉得preorder traversal 加上 '#' mark null node就足够了. 没必要再用
: inorder traversal了. 因为BT serialize/deserialze, preorder + sentinel 就够了.
: 请牛人指教.谢谢.

x*u2015-06-29 07:06

4 楼

cc 150 上是用preorder and inorder, 同时加上sentinel to mark null node.
我觉得inorder是没有必要的.
感觉需要严格的数学证明.
如果tree T contains tree S, T's preorder (with sentinel to mark null) 的
string 肯定 contains S's preorder string.
反方向, 如果T's preorder string contains S's preorder string, 就一定能推出 "
tree T contains tree S"?
如果preorder+sentinel不足够的话, 能不能给个反例来说明 inorder是必须的.

【在 b*******1 的大作中提到】

: 貌似你说的这种null用#来表示的方法就是CC答案上说的诶，应该是make sense的

x*u2015-06-29 07:06

5 楼

you are right.
但是这里, 我们就假设能找有一个special symbol to mark null吧.

【在 s********l 的大作中提到】

: 如果有node的内容就是'#' 这样的Dummy node 就不好用了把~
:
: 了.