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.
f*d
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.
不过感觉不正确， 不同的结构都可能出来一模一样的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
5 楼
感觉不正确， 理由还是，不同的结构都可能出来一模一样的double LL
【在 J****3 的大作中提到】
: 把BT->double LL
: 然后找Intersect 点？
【在 J****3 的大作中提到】
: 把BT->double LL
: 然后找Intersect 点？
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
r*c
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
【在 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
10 楼
加了NULL之后应该没有这个问题，SERIALIZE之后一定是唯一的
【在 f*********d 的大作中提到】
: 好主意~
: 不过感觉不正确， 不同的结构都可能出来一模一样的serialization result~
【在 f*********d 的大作中提到】
: 好主意~
: 不过感觉不正确， 不同的结构都可能出来一模一样的serialization result~
相关阅读
08年没抽中的非stem的也有opt extension么？刚问了老板加入不中的backup plan求助premium processing stopped【求助帖】”逃费“被抓，会影响我找工作么？ (转载)问一个client/server的问题Amazon 店面多长时间没消息就是默据？发个刚面完的rocket fuel的面经吧急！这两个offer怎么选？郁闷 亚马逊onsite面试悲剧其实还不如看悲剧的话多长时间能收到退信求Yelp onsite面经H1B transfer 之后还能在原公司呆多久？求助！有什么办法能让我take这个intership总会有人会抽不中M家的分部yammer-20 分钟数学测试Opt to H1bDallas的2个offer求建议特意发帖吐槽一下linkedin的onsite有人perl熟吗?请教一个命令打扰一下大家，问个401k的问题