a********n
发帖数: 1287 | | S*******0
发帖数: 198 | 2 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);
} | j*****j
发帖数: 201 | 3 这是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);
| a********n
发帖数: 1287 | 4 thanks, 那这个简单多了。
【在 j*****j 的大作中提到】
: 这是Binary Tree的最近祖先寻找法，
: 对BST， 直接从root开始，找到一个节点的数据位于[a,b]之间即为a,b的最近祖先
:
: ){
| n**e
发帖数: 116 | 5 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;
}
}
} | S******t
发帖数: 151 | 6 我的想法是先dfs一次，记住访问时间的那个pair，然后先判断a是否为b的祖先以及b是
否为a的祖先 (括号嵌套定理)，如果不是，沿着a的父亲往根走，判断每个点是否为b的
祖先即可。 | S******t
发帖数: 151 | 7 哦……是BST……看复杂了……那LSS说的方法是比较好的了 | S******t
发帖数: 151 | |
|
