Lowest Common Ancestor
Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.
The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.
http://www.lintcode.com/en/problem/lowest-common-ancestor/
Discussion
可以先取得每个node到root的路径，然后找路径相交的地方就是LCA了。比较麻烦，要先遍历一遍，建立每个node的parent关系。
还有个方法就是devide-conquer。如果root就是A或者B，那么root就是LCA了，不然就分别找root的left和right里A B 是否存在，如果两者都存在，那root就是LCA，不然就是哪个找到了哪个是LCA。
We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.
Solution 1 Bottom-up Approach
//worst case O(n) run time
class Solution {
public:
/**
* @param root: The root of the binary search tree.
* @param A and B: two nodes in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
// write your code here
if(root == NULL || root == A || root==B) {
return root;
}
TreeNode *left = lowestCommonAncestor(root->left, A, B);
TreeNode *right = lowestCommonAncestor(root->right, A, B);
if(left != NULL && right != NULL) {
return root;
}
if(left != NULL)
return left;
if(right != NULL)
return right;
return NULL;
//return L ? L : R;
}
};
Solution 2 Top-Down Approach
class Solution {
public:
/**
* @param root: The root of the binary search tree.
* @param A and B: two nodes in a Binary.
* @return: Return the least common ancestor(LCA) of the two nodes.
*/
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
if(root == NULL) return NULL;
//if the current node is A or B, the current node is the LCA
if(root == A || root == B) return root;
//otherwise we count the number of nodes that matches either A or B in
//the left subtree
int totalMatchesAB = countMatchesAB(root->left, A, B);
if(totalMatchesAB == 1) {//the other match must be in the right subtree
return root;
} else if(totalMatchesAB == 2) {//both are in the left subtree
return lowestCommonAncestor(root->left, A, B);
} else {//==0, both are in the right subtree
return lowestCommonAncestor(root->right, A, B);
}
}
private:
//count the # of nodes that matches A or B in the subtree
int countMatchesAB(TreeNode *root, TreeNode *A, TreeNode *B) {
if(root == NULL) return 0;
int totalMatches = countMatchesAB(root->left, A, B) + countMatchesAB(root->right, A, B);
if(root == A || root == B) {
return 1+totalMatches;
}
return totalMatches;
}
};
- Complexity analysis. If the tree is balanced, run time complexity would be O(n), because each recursion we cut off half of the tree if it is balanced.
- In the worst case the complexity could go up to O(n^2). A degenerated tree is such a case, because the countMatchesAB function traverses the same nodes over and over again.
- Iterative
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *A, TreeNode *B) {
if(root == NULL) return NULL;
//if the current node is A or B, the current node is the LCA
if(root == A || root == B) return root;
//otherwise we count the number of nodes that matches either A or B in
//the left subtree
stack<TreeNode*> stk;
stk.push(root);
while(stk.empty() == false) {
TreeNode *cur = stk.top();
stk.pop();
if(cur == A || cur== B) return cur;
int totalMatchesAB = countMatchesAB(cur->left, A, B);
if(totalMatchesAB == 1) {//the other match must be in the right subtree
return cur;
} else if(totalMatchesAB == 2) {//both are in the left subtree
stk.push(cur->left);
} else {//==0, both are in the right subtree
stk.push(cur->right);
}
}
}