J*3
2 楼
把BT->double LL
然后找Intersect 点?
然后找Intersect 点?
z*g
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.
serialize the b-trees with null mark.
Then, find longest common substring.
recheck if they r not isomorphic.
g*9
6 楼
Re,坐等大侠解答~~
s*e
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不?
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
8 楼
define what do you mean by "equal". especially, are they equal:
root=1, root->left=2
root=1, root->right=2
root=1, root->left=2
root=1, root->right=2
相关阅读
林茵现在还接着招人该如何谢谢这个CCC老板?求建议:Android developer还是Data engineer? (转载)交通部公安部28日正式公布出租车专车新规 (转载)苹果估计早就知道合并的消息读书还是找工作呢?H1B transfer填表LCA, Section B, 7要填New Employment还是Change in Employer30多年从未自愿捐过款,今天给Trump捐了100 (转载)Monster改版后变差了?写一个函数 条用次数很频繁, 比如查询区间之类的大家不要对uber china幸灾乐祸了Credit Karma内推大家看看这个题目改怎么做。东岸 data science /CS内推机会【关于OPT EXT期间换工作入境美国的问题】uber和lyft用狗家地图付费吗?OPT一直pending,公司HR有点不耐烦了请教一下Uber家的码农,怎么看uber中国被滴滴收购?G家的health insurance怎么样?这算java没学好吗?