找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: daisy8867
收起左侧

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

[复制链接]

10

主题

4

精华

251

积分

高级会员

Rank: 3Rank: 3

积分
251
发表于 7-29-2015 11:03 AM | 显示全部楼层
用pair计算有问题,不过你算的结果不对。换成树的先序的序列化字符串就可以了。

14

主题

1

精华

321

积分

高级会员

Rank: 3Rank: 3

积分
321
 楼主| 发表于 7-29-2015 08:42 PM | 显示全部楼层
ufoahw 发表于 7-29-2015 11:03 AM
# b: F5 K  s5 i% @! k) X' C用pair计算有问题,不过你算的结果不对。换成树的先序的序列化字符串就可以了。

1 o6 d* ~9 u2 K/ ^is it? the pre-order sequences of the above trees are [1, 2, 4, 3, 5] and [6, 2, 4, 3, 5] respectively, and the in-order sequences are [4, 2, 1, 3, 5] and [4, 2, 6, 3, 5] respectively, how can you separate them into two trees?- H7 o" K& @- O  V" n
actually, you cannot ask for the common substring, it may be common subsequence, think about the two trees, [1, 2, 3, 4, 6, #, 5, #, #, 8, #, #, #, #, #] and [1, 2, 3, 4, 6, #, 5, 7, #, #, #, #, #, #, #], there are no common strings of both the pre-order sequences and in-order sequences, but [2, 4, 6] is the required common substructure.

10

主题

4

精华

251

积分

高级会员

Rank: 3Rank: 3

积分
251
发表于 7-30-2015 04:41 AM | 显示全部楼层
daisy8867 发表于 7-29-2015 08:42 PM7 I( A& x9 c) y- c
is it? the pre-order sequences of the above trees are [1, 2, 4, 3, 5] and [6, 2, 4, 3, 5] respecti ...
2 r- F' _. ]# v! E( G/ h/ z
...,pair计算有问题,换成序列化之后的字符串再找子串,不是子序列。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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