f*********d
发帖数: 140 | |
J****3
发帖数: 427 | 2 把BT->double LL
然后找Intersect 点？ |
z******g
发帖数: 5 | 3 not sure whether I'm correct or not.
serialize the b-trees with null mark.
Then, find longest common substring.
recheck if they r not isomorphic. |
f*********d
发帖数: 140 | 4 好主意~
不过感觉不正确， 不同的结构都可能出来一模一样的serialization result~
【在 z******g 的大作中提到】
: not sure whether I'm correct or not.
: serialize the b-trees with null mark.
: Then, find longest common substring.
: recheck if they r not isomorphic.
|
f*********d
发帖数: 140 | 5 感觉不正确， 理由还是，不同的结构都可能出来一模一样的double LL
【在 J****3 的大作中提到】
: 把BT->double LL
: 然后找Intersect 点？
|
g***9
发帖数: 159 | |
s**********e
发帖数: 326 | 7 Given two BTs T1 and T2, return the larest common subtree
idea:
step one:
首先分别对T1, T2做预处理，求出每个subtree的nodes总个数，把得到的结果存到
hashtable里面，这一步时间复杂度O(N), N=number of nodes
step two:
从root开始从上到下对每对相对应的node pair，判断以他们为root的subtree是否相同
given node1 from t1, node2 from t2
f(node1,node2)= true if node1 == node2 && f(node1.left, node2.left) && f(
node1.right, node2.right)
这个过程可以使用dp的思想，建个hashtable存放f的值，key=node1.hashcode+"-"+
node2.hashcode， value=boolean
这一步时间复杂度O(N)
step three:
有了第一步的每个subtree 的size, 第二步的每对subtree是否相同，这一步只需要从
root开始找那个最大size的common subtree就可以了
貌似整个算法时间复杂度就是O(N)
大神们看看这个思路work不？ |
c**1
发帖数: 71 | 8 define what do you mean by "equal". especially, are they equal:
root=1, root->left=2
root=1, root->right=2 |
r*c
发帖数: 167 | 9 上面有人提到isomorphic
【在 c**1 的大作中提到】
: define what do you mean by "equal". especially, are they equal:
: root=1, root->left=2
: root=1, root->right=2
|
k*j
发帖数: 153 | 10 加了NULL之后应该没有这个问题，SERIALIZE之后一定是唯一的
【在 f*********d 的大作中提到】
: 好主意~
: 不过感觉不正确， 不同的结构都可能出来一模一样的serialization result~
|
