请问二叉搜索树如何找到两个点的最近祖先？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请问二叉搜索树如何找到两个点的最近祖先？

请问二叉搜索树如何找到两个点的最近祖先？# JobHunting - 待字闺中

l*a2012-01-03 08:01

1 楼

首先买好的牛排，new york strip, rib eye都可以，thick cut
1. 肉从冰箱拿出来放到室温
2. 盐、黑胡椒、vegetable oil，把肉两面抹匀
3. 铸铁锅炉子上烧热到马上要冒烟，转中大火
4. 肉放铸铁锅，一面三分钟，翻面三分钟，侧面一分钟
5. 肉放盘子里，盖上大概五分钟
6. 等肉化冻的时候，芦笋洗干净
7. 等步骤5的时候，铸铁锅放一点油，中小火，芦笋放进去，两面煎熟，撒盐
装盘，整个操作不超过20分钟，火候按自己想吃几分熟掌握，超级容易的大餐
木有图，天天做的菜，懒得拍

a*n2012-01-03 08:01

2 楼

谢谢先。

H*T2012-01-03 08:01

3 楼

你的牛排吃的也太生了。估计在Rare, Medium Rare 之间。我的要在4和5之间加一步
在烤箱里400F 10-20分钟的步骤，达到Medium well或well done.

S*02012-01-03 08:01

4 楼

careerCup
//find lowest common ancestor
//if p and q are on the same side of a node, go to the node's child
//if p and q are on the different side of a node, return the node
//complexity: every node will be reached. Some are multiple times
public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
if(isChild(root.left, p) && isChild(root.left, q))
return LowestCommonAncestor(root.left, p, q);
if(isChild(root.right, p) && isChild(root.right, q))
return LowestCommonAncestor(root.right, p, q);
return root;
}
public boolean isChild(TreeNode root, TreeNode node){
if(root == null) return false;
if(root == node) return true;
return isChild(root.left, node) || isChild(root.right, node);
}

l*a2012-01-03 08:01

5 楼

各人口味不同，你那种做法做出来的在我看来就是不能吃了

【在 H**T 的大作中提到】

: 你的牛排吃的也太生了。估计在Rare, Medium Rare 之间。我的要在4和5之间加一步
: 在烤箱里400F 10-20分钟的步骤，达到Medium well或well done.

j*j2012-01-03 08:01

6 楼

这是Binary Tree的最近祖先寻找法，
对BST，直接从root开始，找到一个节点的数据位于[a,b]之间即为a,b的最近祖先

){

【在 S*******0 的大作中提到】

: careerCup
: //find lowest common ancestor
: //if p and q are on the same side of a node, go to the node's child
: //if p and q are on the different side of a node, return the node
: //complexity: every node will be reached. Some are multiple times
: public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
: if(isChild(root.left, p) && isChild(root.left, q))
: return LowestCommonAncestor(root.left, p, q);
: if(isChild(root.right, p) && isChild(root.right, q))
: return LowestCommonAncestor(root.right, p, q);

s*n2012-01-03 08:01

7 楼

同意！

【在 l**a 的大作中提到】

: 各人口味不同，你那种做法做出来的在我看来就是不能吃了

a*n2012-01-03 08:01

8 楼

thanks, 那这个简单多了。

【在 j*****j 的大作中提到】

: 这是Binary Tree的最近祖先寻找法，
: 对BST，直接从root开始，找到一个节点的数据位于[a,b]之间即为a,b的最近祖先
:
: ){

w*s2012-01-03 08:01

9 楼

牛排建议dry age一下，会更好吃

n*e2012-01-03 08:01

10 楼

Here is my implementation in C++. Just my two cents.
// -------------------------------------------------------------------------
---
// Name: lowestCommonAncestor
// Description: Given two values representing two node's values in a
binary
// search tree, find the lowest common ancestor of the two nodes.
//
// Assumption: We assume those two values are different and both exist in
the
// tree if the tree is not empty.
//
// Node: This algorithm returns root node if one of the values
equals to
// root's value. It can be changed to return NULL instead in this
case.
// -------------------------------------------------------------------------
---
Node* LowestCommonAncestor(Node* root, int value1, int value2) {
using std::max;
using std::min;
using std::cout;
if (!root) return root;
Node* prev = NULL; // Hold the parent node
int small = min(value1, value2);
int large = max(value1, value2);
while(root){
int nodeValue = root->data;
if (large < nodeValue) { // Both values are less than the current node
value
prev = root;
root = root->left; // Go to the left subtree
} else if (small > nodeValue) { // Both values are greater
prev = root;
root = root->right; // Go to the right subtree
} else {

// If the node is one of the two given nodes, their lowest common
ancestor
// is its parent which is prev here
return (nodeValue == value1 || nodeValue == value2) ? prev
: root;
}
}
}

l*a2012-01-03 08:01

11 楼

那就不符合又快又好的标准了

【在 w*********s 的大作中提到】

: 牛排建议dry age一下，会更好吃

S*t2012-01-03 08:01

12 楼

我的想法是先dfs一次，记住访问时间的那个pair，然后先判断a是否为b的祖先以及b是
否为a的祖先 (括号嵌套定理)，如果不是，沿着a的父亲往根走，判断每个点是否为b的
祖先即可。

H*T2012-01-03 08:01

13 楼

既然是天天做的菜，不妨今晚拍个照，鉴赏一下你的成品，最好也来过横断面流着血的。

【在 l**a 的大作中提到】

: 首先买好的牛排，new york strip, rib eye都可以，thick cut
: 1. 肉从冰箱拿出来放到室温
: 2. 盐、黑胡椒、vegetable oil，把肉两面抹匀
: 3. 铸铁锅炉子上烧热到马上要冒烟，转中大火
: 4. 肉放铸铁锅，一面三分钟，翻面三分钟，侧面一分钟
: 5. 肉放盘子里，盖上大概五分钟
: 6. 等肉化冻的时候，芦笋洗干净
: 7. 等步骤5的时候，铸铁锅放一点油，中小火，芦笋放进去，两面煎熟，撒盐
: 装盘，整个操作不超过20分钟，火候按自己想吃几分熟掌握，超级容易的大餐
: 木有图，天天做的菜，懒得拍

S*t2012-01-03 08:01

14 楼

哦……是BST……看复杂了……那LSS说的方法是比较好的了

s*n2012-01-03 08:01

15 楼

你买块生肉回家切开，横断面会流血吗？流血牛排那是做的不对。楼主最后醒5分钟稍
微短了点，时间够长再生也不会流血。

的。

【在 H**T 的大作中提到】

: 既然是天天做的菜，不妨今晚拍个照，鉴赏一下你的成品，最好也来过横断面流着血的。

S*t2012-01-03 08:01

16 楼

我给的那个方法是对二叉树找祖先的 -0-

l*a2012-01-03 08:01

17 楼