Title
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
找公共祖先
Solution
以下只能应用于二叉排序树
//cpp:
//以下只能应用于二叉排序树
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while (root != p && root != q) {
if (p->val <= root->val && q->val <= root->val)
root = root->left;
else {
if (p->val >= root->val && q->val >= root->val)
root = root->right;
else
break;
}
}
return root;
}
Check where p and q exist:
If either p or q is the root, then return the root
If both p and q are in the left subtree, then recursively check for LCA in root->left
If both p and q are in the right subtree, then recursively check for LCA in root->right
Otherwise, we know that p and q are in separate subtrees, so return the current root as the LCA.
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return go(root,p,q);
}
private:
bool find(TreeNode* root, TreeNode* target){
if (!root) return false;
return root==target ? true : find(root->left,target) || find(root->right,target);
}
TreeNode* go(TreeNode* root, TreeNode* p, TreeNode* q){
if (root==p || root==q) return root;
if (find(root->left,p) && find(root->left,q)) return go(root->left,p,q);
if (find(root->right,p) && find(root->right,q)) return go(root->right,p,q);
return root;
}
};
More Concisely: Same concept as above, but the find() function isn’t needed, just go()…
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return go(root,p,q);
}
private:
TreeNode* go(TreeNode* root, TreeNode* p, TreeNode* q){
if (root==p || root==q) return root;
auto left=(root->left) ? go(root->left,p,q) : nullptr;
auto right=(root->right) ? go(root->right,p,q) : nullptr;
return (left && right) ? root : (left) ? left : right;
}
};