找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: daisy8867
收起左侧

[面经题目讨论] 任意两棵树的最大公共子结构

[复制链接]

14

主题

1

精华

321

积分

高级会员

Rank: 3Rank: 3

积分
321
 楼主| 发表于 7-27-2015 08:29 PM | 显示全部楼层
ufoahw 发表于 7-27-2015 03:13 PM
& m9 J6 _% n, X6 ~8 s4 q; Z! ~# y先中序遍历两颗树得到相应树的中序序列,然后求最大公共子串。

1 w% D  m. i5 @+ Y- v! k$ e  n2 ~two different trees may have the same inorder traversal sequence.

10

主题

4

精华

251

积分

高级会员

Rank: 3Rank: 3

积分
251
发表于 7-28-2015 02:34 AM | 显示全部楼层
daisy8867 发表于 7-27-2015 08:29 PM( o1 U9 s) K) p- W4 H$ R
two different trees may have the same inorder traversal sequence.
& q% Q  ?" ^; b* X) K1 a) r
对,就用中序和先序的序列组成一个pair的序列,然后求lcs.

14

主题

1

精华

321

积分

高级会员

Rank: 3Rank: 3

积分
321
 楼主| 发表于 7-28-2015 08:25 PM | 显示全部楼层
ufoahw 发表于 7-28-2015 02:34 AM6 v7 W8 a' ]* f
对,就用中序和先序的序列组成一个pair的序列,然后求lcs.
5 O& h/ E: }) a% a
not really, think about the case: the first tree is [1, 2, 3, 4, #, #, 5], the second one is [6, 2, 3, 4, #, #, 5], the left and right subtrees are both largest common sub-structs with two nodes, the algs you propose will return a tree whose inorder sequence is [4, 2, 3, 5], preorder sequence is [2, 4, 3, 5], thus construct a tree of [2, 4, 3, #, #, #, 5]
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表