任意两棵树的最大公共子结构

ufoahw

用pair计算有问题，不过你算的结果不对。换成树的先序的序列化字符串就可以了。

daisy8867

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?
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.

ufoahw

daisy8867 发表于 7-29-2015 08:42 PM
is it? the pre-order sequences of the above trees are [1, 2, 4, 3, 5] and [6, 2, 4, 3, 5] respecti ...

...，pair计算有问题，换成序列化之后的字符串再找子串，不是子序列。