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

daisy8867

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.

ufoahw

daisy8867 发表于 7-27-2015 08:29 PM
two different trees may have the same inorder traversal sequence.

对，就用中序和先序的序列组成一个pair的序列，然后求lcs.

daisy8867

ufoahw 发表于 7-28-2015 02:34 AM
对，就用中序和先序的序列组成一个pair的序列，然后求lcs.

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]