f*******r
发帖数: 1086 | 1 我知道topcoder上有一个页面讲述RMQ方法，
但是觉得那个方法比较复杂貌似，在面试的时候适宜用那种方法
回答吗？
当然如果允许每个node拥有parent pointer，这个问题比较简单
找出两条从node到root的path，然后找到两条path从底至上的第
一个交点。
如果不允许使用parent pointer，有什么好的办法可以求BTree
的LCA吗？
请知道的大侠赐教一下，非常感谢了！ |
f*********5
发帖数: 576 | 2 why need parent pointer?
why 从底至上?why not 从上至底?
both of the two path should start from root
and u just need to find the last common node
of the two paths
【在 f*******r 的大作中提到】
: 我知道topcoder上有一个页面讲述RMQ方法，
: 但是觉得那个方法比较复杂貌似，在面试的时候适宜用那种方法
: 回答吗？
: 当然如果允许每个node拥有parent pointer，这个问题比较简单
: 找出两条从node到root的path，然后找到两条path从底至上的第
: 一个交点。
: 如果不允许使用parent pointer，有什么好的办法可以求BTree
: 的LCA吗？
: 请知道的大侠赐教一下，非常感谢了！
|
D***h
发帖数: 183 | 3 你自己写一下就知道为什么了。
【在 f*********5 的大作中提到】
: why need parent pointer?
: why 从底至上?why not 从上至底?
: both of the two path should start from root
: and u just need to find the last common node
: of the two paths
|
s********l
发帖数: 998 | 4 什么是RMQ方法啊？
//刚才说错了，想到另外一个题去了。。。
我土问一下，你们都是在topcoder哪里找题目看的？
【在 f*******r 的大作中提到】
: 我知道topcoder上有一个页面讲述RMQ方法，
: 但是觉得那个方法比较复杂貌似，在面试的时候适宜用那种方法
: 回答吗？
: 当然如果允许每个node拥有parent pointer，这个问题比较简单
: 找出两条从node到root的path，然后找到两条path从底至上的第
: 一个交点。
: 如果不允许使用parent pointer，有什么好的办法可以求BTree
: 的LCA吗？
: 请知道的大侠赐教一下，非常感谢了！
|
f*********5
发帖数: 576 | 5 1) do recursion to find the two nodes in the tree
then we can get the path from root to node.
2) compare the two paths.
doesn't this work?
【在 D***h 的大作中提到】
: 你自己写一下就知道为什么了。
|
f*******r
发帖数: 1086 | 6 RMQ指的是Range Minimum Query
具体可以看这个link：
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
我只是看了一下别人推荐的topcoder这个algorithm tutorial.
【在 s********l 的大作中提到】
: 什么是RMQ方法啊？
: //刚才说错了，想到另外一个题去了。。。
: 我土问一下，你们都是在topcoder哪里找题目看的？
|
f*******r
发帖数: 1086 | 7 如果是BST，应该比较容易找到从root到node的
path，因为知道应该向左还是向右，普通的
binary tree没有这个性质，貌似需要遍历
所有的node才能找到input的node，所以
如果有了parent pointer，会比较容易一些。
【在 f*********5 的大作中提到】
: 1) do recursion to find the two nodes in the tree
: then we can get the path from root to node.
: 2) compare the two paths.
: doesn't this work?
|
f*********5
发帖数: 576 | 8 u r right
but
1) you want high efficiency
2) you don't want extra memory usage
3) you don't like complex algorithm
...
sigh,is there so easy thing in the world?
【在 f*******r 的大作中提到】
: 如果是BST，应该比较容易找到从root到node的
: path，因为知道应该向左还是向右，普通的
: binary tree没有这个性质，貌似需要遍历
: 所有的node才能找到input的node，所以
: 如果有了parent pointer，会比较容易一些。
|
y*c
发帖数: 904 | 9
The best way I can think of is to traverse the tree but use a stack or
vector to maintain the ancestors of current node during the traversal. Then
copy the ancestor vector/stack when the node is input node1 or node2. Then
search the LCA.
【在 f*******r 的大作中提到】
: 如果是BST，应该比较容易找到从root到node的
: path，因为知道应该向左还是向右，普通的
: binary tree没有这个性质，貌似需要遍历
: 所有的node才能找到input的node，所以
: 如果有了parent pointer，会比较容易一些。
|
d*******r
发帖数: 23 | 10 "Programming Interviews Exposed" has the solution. One of the properties
of BST is that left subtree nodes is always smaller than right subtree
nodes. So all you need to do is to iterate through the BST from the root
and find the first node that is lesser than one node and greater than
the other node. Pseudo code:
If valuel and value2 are less than the current node's value
Examine the left child
If valuel and value2 are greater than the current node's value
Examine the right child
Otherwise
The
【在 f*******r 的大作中提到】
: 我知道topcoder上有一个页面讲述RMQ方法，
: 但是觉得那个方法比较复杂貌似，在面试的时候适宜用那种方法
: 回答吗？
: 当然如果允许每个node拥有parent pointer，这个问题比较简单
: 找出两条从node到root的path，然后找到两条path从底至上的第
: 一个交点。
: 如果不允许使用parent pointer，有什么好的办法可以求BTree
: 的LCA吗？
: 请知道的大侠赐教一下，非常感谢了！
|
s****h
发帖数: 15 | 11 你这个是针对 BST的， general 的 binary tree并没有这个特点，所以不work.
【在 d*******r 的大作中提到】
: "Programming Interviews Exposed" has the solution. One of the properties
: of BST is that left subtree nodes is always smaller than right subtree
: nodes. So all you need to do is to iterate through the BST from the root
: and find the first node that is lesser than one node and greater than
: the other node. Pseudo code:
: If valuel and value2 are less than the current node's value
: Examine the left child
: If valuel and value2 are greater than the current node's value
: Examine the right child
: Otherwise
|
