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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 好主意~ : 不过感觉不正确, 不同的结构都可能出来一模一样的serialization result~
|