k*******r
发帖数: 355 | | G**********s
发帖数: 70 | | n**4
发帖数: 719 | 3 2楼进化树能展开说一下吗？
我有一个解法 记得是版上某大牛做的
basic idea: use a hash function to get a digest of a tree by hashing its
child subtrees' digests:
digest(tree)=0 if tree is empty
digest(tree)=hash(digest(LeftChildTree),digest(RightChildTree),rootVal)
therefore, this problem can be solved by a post-order traversal. On the
traversal, all the subtrees are digested and registered. If a match occurs,
the roots of both trees and their size are compared and recorded.
the hashTable_get/put functions need the tree digest (hash value) for quick
access, and also the tree root address to perform verification in the
unlikely case of collision.
// this function returns the size of the tree rooted by "root", and gives
its digest, the max matched subtrees in it (and the size of the matched
subtree)
int maxMatchSubtree(BT * root, int * digest, hashTable * T, BT ** sub1, BT *
* sub2, int * size) {
int sl,sr,lsize,rsize,ldigest,rdigest,thisSize;
BT * subL1, *subL2, *subR1, *subR2;
if (!root) {
*digest=0;
*size=0;
return 0;
}
sl=maxMatchSubtree(root->L, &ldigest, T, &subL1, &subL2, &lsize);
sr=maxMatchSubtree(root->R, &rdigest, T, &subR1, &subR2, &rsize);
thisSize=sl+sr+1;
*digest=hash(ldigest, rdigest, root->val);
if (*sub1=hashTable_get(*digest, root)) {
// entire tree matches record
*size=thisSize;
*sub2=root;
} else {
hashTable_put(*digest, root);
if (lsize>=rsize) {
*size=lsize;
*sub1=subL1;
*sub2=subL2;
} else {
*size=rsize;
*sub1=subR1;
*sub2=subR2;
}
}
return thisSize;
} | f*********i
发帖数: 197 | 4 可以把两个树A,B分别preorder,inorder遍历
然后问题就变成
longest common string in preorder[A], preorder[B] => string 1
longest common string in inorder[A], inorder[B] => string 2
最后再次longest common string in string 1，string 2
如果全部用KMP来做，时间复杂度O(n) | s*******n
发帖数: 97 | | p********n
发帖数: 20 | 6 首先遍历一下求出两棵树的欧拉序列；问题转化求两个序列的最长*连续*公共子串。
但是由于两棵树是独立编号的，这导致两棵树中structure相同的子树在各自的欧拉序
列中可能相差一个常数；所以需要处理一下欧拉序列，可以这样变换：(A[0],...,A[n-
1])-->(A[1]-A[0],...,A[n-1]-A[n-2])。
剩下的就是求最长连续公共子串，可以后缀数组搞定。
整个过程中，遍历O(n+m)，求最长连续公共子串O(n+m)，所以总复杂度也是O(n+m)。n,
m是两棵树的节点数。
【在 k*******r 的大作中提到】
: 找二叉树 两个最大的相同子树,这个怎么做
| m****i
发帖数: 650 | | n**4
发帖数: 719 | 8 这个问题真的等同于求连续最长子串吗？
展开的字符串 和原来的树 不是一一对应的关系吧 | p********n
发帖数: 20 | 9 对二叉树进行DFS，将遍历过程中遇到的节点按顺序记下，得到一个长度为2N-1的节点
序列，就是欧拉序列。
【在 m****i 的大作中提到】
: 什么是欧拉序列？
| k*******r
发帖数: 355 | 10 我觉得把找两个最大相同子树转换为找两个最长公共子串的思路不对。
因为不是所有子串都对应子树的，有些子串横跨了两颗子树， 这些子串不能看作“合
法”的子串。在算法中至少得考虑这一点 |
|
