由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问一道题(1)
相关主题
问一道算法题问一个题目
问一道二叉树serialize的问题A onsite被拒,面经,求分析失败原因
serialize tree可否用in order或者post order150上这个是不是不对? (转载)
问一道n-ary tree 的题目How can one determine whether a singly linked list has a cycle?
serialize n-ary tree 一问面试的时候 binary tree的delete也要15分钟之内写完么?
如何 serialization 和deserialization hash table ?问个二叉树删除结点的问题
问最小窗口覆盖的面试题CCI 4.2 答案是不是错了,不是一次bfs 而是要 2次 dfs的
Least Common Ancester算法最优解那个双堆求median的能不能这样做?
相关话题的讨论汇总
话题: root话题: subtree话题: node2话题: node1话题: isomorphic
进入JobHunting版参与讨论
1 (共1页)
f*********d
发帖数: 140
1
找二叉树两个最大的相同子树
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
6
Re,坐等大侠解答~~
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~

1 (共1页)
进入JobHunting版参与讨论
相关主题
那个双堆求median的能不能这样做?serialize n-ary tree 一问
报Google Offer并请教面试题如何 serialization 和deserialization hash table ?
一道题:2个BST,按大小顺序打印两棵树的所有节点问最小窗口覆盖的面试题
LCA复杂度是多少Least Common Ancester算法最优解
问一道算法题问一个题目
问一道二叉树serialize的问题A onsite被拒,面经,求分析失败原因
serialize tree可否用in order或者post order150上这个是不是不对? (转载)
问一道n-ary tree 的题目How can one determine whether a singly linked list has a cycle?
相关话题的讨论汇总
话题: root话题: subtree话题: node2话题: node1话题: isomorphic