s*******r
发帖数: 47 | 1 找 二叉树 两个最大的相同子树
没答上来。
见了四个，被拒了。 第二个是manager，后来主动写信跟我联系，说把我推荐给industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求祝福！ |
b*******y
发帖数: 1240 | 2 bless
这道题有没有正解
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！
【在 s*******r 的大作中提到】
: 找 二叉树 两个最大的相同子树
: 没答上来。
: 见了四个，被拒了。 第二个是manager，后来主动写信跟我联系，说把我推荐给industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求祝福！
|
g***s
发帖数: 3811 | 3 Why? there is O(n) algo. O(n) space and O(n) time.
but anyway, bless lz.
【在 b*******y 的大作中提到】
: bless
: 这道题有没有正解
:
: industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
: 难吧？ 求祝福！
|
C***y
发帖数: 2546 | 4 稍微详细说一下？
【在 g***s 的大作中提到】
: Why? there is O(n) algo. O(n) space and O(n) time.
: but anyway, bless lz.
|
g***s
发帖数: 3811 | 5 Mark nodes from leaves(height from 0) based on left/right node. and put
into hashmap.
hashmap : (left_node_marked_value,right_node_marked_value) ->
marked_value
marked_value = 0 ;
if ( (left_node.marked_value,right_node.marked_value) is not in the map)
{
map[(left_node_marked_value,right_node_marked_value)] =
marked_value++;
}
current_node.marled_value =
map[(left_node_marked_value,right_node_marked_value);
BTW:
A subtree of a tree T is a tree consisting of a node in T and all of its
descendants in T.
【在 C***y 的大作中提到】
: 稍微详细说一下？
|
C***y
发帖数: 2546 | 6 谢谢！
先mark一下，晚上回去仔细研究一下
【在 g***s 的大作中提到】
: Mark nodes from leaves(height from 0) based on left/right node. and put
: into hashmap.
: hashmap : (left_node_marked_value,right_node_marked_value) ->
: marked_value
: marked_value = 0 ;
: if ( (left_node.marked_value,right_node.marked_value) is not in the map)
: {
: map[(left_node_marked_value,right_node_marked_value)] =
: marked_value++;
: }
|
g*********s
发帖数: 1782 | 7 so after you build up a hash map like this, how do you give the maximum
sub-tree?
【在 g***s 的大作中提到】
: Mark nodes from leaves(height from 0) based on left/right node. and put
: into hashmap.
: hashmap : (left_node_marked_value,right_node_marked_value) ->
: marked_value
: marked_value = 0 ;
: if ( (left_node.marked_value,right_node.marked_value) is not in the map)
: {
: map[(left_node_marked_value,right_node_marked_value)] =
: marked_value++;
: }
|
g***s
发帖数: 3811 | 8 Go through from leaves, find two max_depth nodes with same marked
values.
It can be done when we build it. Just change a little. (use map point
the first node)
if ( (left_node.marked_value,right_node.marked_value) is not in the map)
{
map[(left_node_marked_value,right_node_marked_value)] = current_node;
} else {
result = (current_node's subtree ,
map[(left_node_marked_value,right_node_marked_value)]'s subtree);
}
current_node.marled_value =
map[(left_node_marked_value,right_node_marked_value);
maximum
【在 g*********s 的大作中提到】
: so after you build up a hash map like this, how do you give the maximum
: sub-tree?
|
g*********s
发帖数: 1782 | 9 sorry, the problem is given two bt's and find the maximum identical sub-tree of
these two, or given one bt and find the maximum sub-tree in this bt?
【在 g***s 的大作中提到】
: Go through from leaves, find two max_depth nodes with same marked
: values.
: It can be done when we build it. Just change a little. (use map point
: the first node)
: if ( (left_node.marked_value,right_node.marked_value) is not in the map)
: {
: map[(left_node_marked_value,right_node_marked_value)] = current_node;
: } else {
: result = (current_node's subtree ,
: map[(left_node_marked_value,right_node_marked_value)]'s subtree);
|
s*******r
发帖数: 47 | 10 给一个二叉数，找这个树中两个相同子树，并且使它们是最大的相同子树， 意思是没
有两个相同子树size比它们更大。
tree of
【在 g*********s 的大作中提到】
: sorry, the problem is given two bt's and find the maximum identical sub-tree of
: these two, or given one bt and find the maximum sub-tree in this bt?
|
|
|
g*********s
发帖数: 1782 | 11 so have u gotten grass' idea? i don't get it yet.
【在 s*******r 的大作中提到】
: 给一个二叉数，找这个树中两个相同子树，并且使它们是最大的相同子树， 意思是没
: 有两个相同子树size比它们更大。
:
: tree of
|
s*******r
发帖数: 47 | 12 I did not get it either. I did not see any comparation happened in glass's
alg. Could anybody give a more clear explanation? Is there other way to
solve it?
【在 g*********s 的大作中提到】
: so have u gotten grass' idea? i don't get it yet.
|
o****d
发帖数: 2835 | 13 大致是说
如果左右子树一样 那么这棵树一样
用map就可以查到之前是否已经有同样子树的树
有的话就发现同样的子树
没有就插入
直到把每个节点都遍历 返回最大的那个就是了
【在 g*********s 的大作中提到】
: so have u gotten grass' idea? i don't get it yet.
|
o****d
发帖数: 2835 | 14 那个算法中的比较就是发生在
map插入的时候
【在 s*******r 的大作中提到】
: I did not get it either. I did not see any comparation happened in glass's
: alg. Could anybody give a more clear explanation? Is there other way to
: solve it?
|
g*********s
发帖数: 1782 | 15 要求树结构一样，怎么用一个字数属性的比较来表示？
【在 o****d 的大作中提到】
: 大致是说
: 如果左右子树一样 那么这棵树一样
: 用map就可以查到之前是否已经有同样子树的树
: 有的话就发现同样的子树
: 没有就插入
: 直到把每个节点都遍历 返回最大的那个就是了
|
h*****1
发帖数: 74 | 16 how about this:
in-order traversal to get a string. then use suffix tree to find the two
identical strings. it is O(n) time and O(n) space. |
s*******r
发帖数: 47 | 17 刚刚打了一下瞌睡，居然来了点灵感， 这不是类似于求两个最大的substring吗？ 我
怎么那么蠢呢？ |
s*******r
发帖数: 47 | |
s*******r
发帖数: 47 | |
s*******r
发帖数: 47 | 20 老兄眼快脑快
【在 h*****1 的大作中提到】
: how about this:
: in-order traversal to get a string. then use suffix tree to find the two
: identical strings. it is O(n) time and O(n) space.
|
|
|
h*****1
发帖数: 74 | 21 唉，一个onsite 也没拿到。
【在 s*******r 的大作中提到】
: 老兄眼快脑快
|
g******0
发帖数: 221 | 22 I am sorry, I don't quite understand what the problem is:
Given a binary Search Tree, find two biggest same subtrees.???
二叉树 是 binary search tree, or binary tree?
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！
【在 s*******r 的大作中提到】
: 找 二叉树 两个最大的相同子树
: 没答上来。
: 见了四个，被拒了。 第二个是manager，后来主动写信跟我联系，说把我推荐给industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求祝福！
|
g*********s
发帖数: 1782 | 23 i don't think this is right.
here the question is the structure isophormism, not the data the same.
for example, the tree could have all node data 1. then the tree is 1111111..
. after travesal. the structure info is lost.
【在 s*******r 的大作中提到】
: 老兄眼快脑快
|
o****d
发帖数: 2835 | 24 agree
..
【在 g*********s 的大作中提到】
: i don't think this is right.
: here the question is the structure isophormism, not the data the same.
: for example, the tree could have all node data 1. then the tree is 1111111..
: . after travesal. the structure info is lost.
|
g******0
发帖数: 221 | 25 那么多人在讨论问题，为什么没有人回我啊？可不可以把题么说说清楚？或是翻译to
English?
【在 g******0 的大作中提到】
: I am sorry, I don't quite understand what the problem is:
: Given a binary Search Tree, find two biggest same subtrees.???
: 二叉树 是 binary search tree, or binary tree?
:
: industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
: 难吧？ 求祝福！
|
h*****1
发帖数: 74 | 26 大家都明白阿。不知还要怎么解释。
【在 g******0 的大作中提到】
: 那么多人在讨论问题，为什么没有人回我啊？可不可以把题么说说清楚？或是翻译to
: English?
|
o****d
发帖数: 2835 | 27 二叉树 是 binary tree
binary search tree 是 二叉查找树
题目就是你说的那个意思
这里的一样指的是结构上一样
【在 g******0 的大作中提到】
: I am sorry, I don't quite understand what the problem is:
: Given a binary Search Tree, find two biggest same subtrees.???
: 二叉树 是 binary search tree, or binary tree?
:
: industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
: 难吧？ 求祝福！
|
s*******r
发帖数: 47 | 28 楼上有道理， 最大substring是必要条件不是充分条件 |
s*****y
发帖数: 897 | 29 你怎么保证你找到的最大两个子串的头尾都是leaf
除非你在每个node那里加多一个变量mark是不是leaf
【在 h*****1 的大作中提到】
: how about this:
: in-order traversal to get a string. then use suffix tree to find the two
: identical strings. it is O(n) time and O(n) space.
|
g***s
发帖数: 3811 | 30 解释一下我的算法：
所有两个节点，如果以它为根的树相同，就mark成相同的元素（或数字）
所有两个节点，如果它们的左子树和右子树都被mark成相同了，那么这两个节点也认为
相同。
例如，所有的叶节点，都相同。我们mark成0
然后，看depth=1的节点。如果（left,right)=(0，NULL)的节点mark成1 （NULL，0）
的mark成2
再看depth=3的。。。一直递推到root
有点像DP。
改进的算法，就是不用0,1,2,3..来mark，而是用满足的第一个点来mark。这样，第二
个相同的点就可以和第一个点构成相同子树。 |
|
|
g*********s
发帖数: 1782 | 31 明白你的思路了。不过这个改进是什么？
【在 g***s 的大作中提到】
: 解释一下我的算法：
: 所有两个节点，如果以它为根的树相同，就mark成相同的元素（或数字）
: 所有两个节点，如果它们的左子树和右子树都被mark成相同了，那么这两个节点也认为
: 相同。
: 例如，所有的叶节点，都相同。我们mark成0
: 然后，看depth=1的节点。如果（left,right)=(0，NULL)的节点mark成1 （NULL，0）
: 的mark成2
: 再看depth=3的。。。一直递推到root
: 有点像DP。
: 改进的算法，就是不用0,1,2,3..来mark，而是用满足的第一个点来mark。这样，第二
|
g***s
发帖数: 3811 | 32 原始算法在5楼（用数字mark）。改进的在8楼（用第一个满足的node mark）
【在 g*********s 的大作中提到】
: 明白你的思路了。不过这个改进是什么？
|
g*********s
发帖数: 1782 | 33 感觉这个解法还是有问题。你这个编码最后的范围是什么？
假设n节点的二叉树有f(n)个，对每个不同子树，编码是sum(f(n-k)) + i，k = 1..n-1 ，i = 1..f(n)？如果是这样的话，编码最后可能变的很大啊。
【在 g*********s 的大作中提到】
: 明白你的思路了。不过这个改进是什么？
|
g***s
发帖数: 3811 | 34 还是没明白啊。
这个是染色的思路。不是编码。
-1 ，i =
1..f(n)？如果是这样的话，编码最后可能变的很大啊。
【在 g*********s 的大作中提到】
: 感觉这个解法还是有问题。你这个编码最后的范围是什么？
: 假设n节点的二叉树有f(n)个，对每个不同子树，编码是sum(f(n-k)) + i，k = 1..n-1 ，i = 1..f(n)？如果是这样的话，编码最后可能变的很大啊。
|
x******g
发帖数: 41 | 35 请问叶子节点为啥都是0，不用考虑他们本身的值嘛？
【在 g***s 的大作中提到】
: 解释一下我的算法：
: 所有两个节点，如果以它为根的树相同，就mark成相同的元素（或数字）
: 所有两个节点，如果它们的左子树和右子树都被mark成相同了，那么这两个节点也认为
: 相同。
: 例如，所有的叶节点，都相同。我们mark成0
: 然后，看depth=1的节点。如果（left,right)=(0，NULL)的节点mark成1 （NULL，0）
: 的mark成2
: 再看depth=3的。。。一直递推到root
: 有点像DP。
: 改进的算法，就是不用0,1,2,3..来mark，而是用满足的第一个点来mark。这样，第二
|
g***s
发帖数: 3811 | 36 我的理解是只考虑树的形状。
两个子树有所有对应的点。
【在 x******g 的大作中提到】
: 请问叶子节点为啥都是0，不用考虑他们本身的值嘛？
|
g*********s
发帖数: 1782 | 37 这么说吧。假设左子树拿到p，右子树拿到q，那根的编码是什么？
递归表达式：
c(r) = 0 if r->left == r->right == NULL;
c(r) = 1 if r->left != NULL && c(r->left) && r->right == NULL;
c(r) = 2 if r->left == NULL && r->right != NULL && c(r->right) == 0
otherwise, c(r) = f(c(r->left), c(r->right)).
but what is f(m, n) here?
【在 g***s 的大作中提到】
: 还是没明白啊。
: 这个是染色的思路。不是编码。
:
: -1 ，i =
: 1..f(n)？如果是这样的话，编码最后可能变的很大啊。
|
x******g
发帖数: 41 | 38 明白啦
【在 g***s 的大作中提到】
: 我的理解是只考虑树的形状。
: 两个子树有所有对应的点。
|
x******g
发帖数: 41 | 39 你想的太复杂了
画两棵树
从叶子节点一层层上去写出来
【在 g*********s 的大作中提到】
: 这么说吧。假设左子树拿到p，右子树拿到q，那根的编码是什么？
: 递归表达式：
: c(r) = 0 if r->left == r->right == NULL;
: c(r) = 1 if r->left != NULL && c(r->left) && r->right == NULL;
: c(r) = 2 if r->left == NULL && r->right != NULL && c(r->right) == 0
: otherwise, c(r) = f(c(r->left), c(r->right)).
: but what is f(m, n) here?
|
g*****i
发帖数: 2162 | 40 这里的相同是结构相同吗?
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！
【在 s*******r 的大作中提到】
: 找 二叉树 两个最大的相同子树
: 没答上来。
: 见了四个，被拒了。 第二个是manager，后来主动写信跟我联系，说把我推荐给industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求祝福！
|
|
|
g***s
发帖数: 3811 | 41 if the value of the node needs to be considered, we only need to change a
little in the algo.
same time/space complexity.
【在 x******g 的大作中提到】
: 明白啦
|
c**r
发帖数: 108 | 42 Mark
industry
recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求
祝福！
【在 s*******r 的大作中提到】
: 找 二叉树 两个最大的相同子树
: 没答上来。
: 见了四个，被拒了。 第二个是manager，后来主动写信跟我联系，说把我推荐给industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求祝福！
|
q*c
发帖数: 9453 | 43 而且这个 substring 不能保证在一个node 下面， 这就土了。
我一开始也准备这么干来着。
1111111
【在 o****d 的大作中提到】
: agree
:
: ..
|
m*********2
发帖数: 701 | 44 见了四个？
还是先别就面试吧。 延迟一个或两个月， 回家苦读书
MS最少三个。 要见七个才算成功 （还不是100%）
第三个那个对你不满意， 第四个也不满意
industry
recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求
祝福！
【在 s*******r 的大作中提到】
: 找 二叉树 两个最大的相同子树
: 没答上来。
: 见了四个，被拒了。 第二个是manager，后来主动写信跟我联系，说把我推荐给industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求祝福！
|
p*****a
发帖数: 147 | 45
Go through from leaves, find two max_depth nodes with same marked
values.
It can be done when we build it. Just change a little. (use map point
the first node)
if ( (left_node.marked_value,right_node.marked_value) is not in the map)
{
map[(left_node_marked_value,right_node_marked_value)] = current_node;
} else {
result = (current_node's subtree ,
map[(left_node_marked_value,right_node_marked_value)]'s subtree);
}
current_node.marled_value =
map[(left_node_marked_value,right_node_marked_value);
~~~~~~~~~~~~~~~~~~~~~有点搞糊涂了，节点的marked_value = 一个节点？如果一个新
节点的子树与另一个节点的子树相同，他们的(left_node.marked_value,right_node.
marked_value) 也不应该相同吧？那你怎么前面用if ( (left_node.marked_value,
right_node.marked_value) is not in the map) 来做判断？
【在 g***s 的大作中提到】
: Go through from leaves, find two max_depth nodes with same marked
: values.
: It can be done when we build it. Just change a little. (use map point
: the first node)
: if ( (left_node.marked_value,right_node.marked_value) is not in the map)
: {
: map[(left_node_marked_value,right_node_marked_value)] = current_node;
: } else {
: result = (current_node's subtree ,
: map[(left_node_marked_value,right_node_marked_value)]'s subtree);
|
g**e
发帖数: 6127 | 46 相同。请再仔细领会一下大牛代码的精神
【在 p*****a 的大作中提到】
:
: Go through from leaves, find two max_depth nodes with same marked
: values.
: It can be done when we build it. Just change a little. (use map point
: the first node)
: if ( (left_node.marked_value,right_node.marked_value) is not in the map)
: {
: map[(left_node_marked_value,right_node_marked_value)] = current_node;
: } else {
: result = (current_node's subtree ,
|
g****v
发帖数: 971 | 47 为什么inorder，pre-order and post-order不行么？
【在 s*******r 的大作中提到】
: inorder遍历，
: 求两个最长的相同子串
|
p*****a
发帖数: 147 | 48 got it.
Thanks.
【在 g**e 的大作中提到】
: 相同。请再仔细领会一下大牛代码的精神
|
s*******f
发帖数: 1114 | 49 no good idea,but:
preorder and inorder can uniquely define a btree, let me begin with here.
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！
【在 s*******r 的大作中提到】
: 找 二叉树 两个最大的相同子树
: 没答上来。
: 见了四个，被拒了。 第二个是manager，后来主动写信跟我联系，说把我推荐给industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求祝福！
|
