Lowest Common Ancestor II
Following up the previous question. The node has an extra attribute parent which point to the father of itself. The root's parent is null.
http://www.lintcode.com/en/problem/lowest-common-ancestor-ii/
Discussion
We trace from the two nodes to root, eventually the two paths will join together. Use a hash set to record those visted nodes on the path. Once we reached the first node that has been visted, we immediately return that node as the LCA. Because it means that that node has been visited by the other path, i.e., it the the first place where the two path joins, -- LCA.
Solution
class Solution {
public:
/**
* @param root: The root of the tree
* @param A, B: Two node in the tree
* @return: The lowest common ancestor of A and B
*/
ParentTreeNode *lowestCommonAncestorII(ParentTreeNode *root,
ParentTreeNode *A,
ParentTreeNode *B) {
if(root == NULL || A == NULL || B == NULL) return NULL;
unordered_set<ParentTreeNode*> myset;
while (A != NULL || B!= NULL) {
if(A != NULL) {
if(myset.emplace(A).second == true) {
A = A->parent;//trace up to root
} else {//A has been visited in the other path
return A;
}
}
if(B != NULL) {
if(myset.emplace(B).second == true) {
B = B->parent;
} else {
return B;
}
}
}
return NULL;
}
};
The run time complexity of this approach is O(h), where h is the tree’s height. The space complexity is also O(h), since it can mark at most 2h nodes.
Follow Up
Is there some way to save the extra space for the hash set? The idea is :
Once we knew both heights, we could subtract from one another and get the height’s difference (dh). If you observe carefully from the previous solution, the node which is closer to the root is always dh steps ahead of the deeper node. We could eliminate the need of marking visited nodes altogether.
class Solution {
public:
/**
* @param root: The root of the tree
* @param A, B: Two node in the tree
* @return: The lowest common ancestor of A and B
*/
ParentTreeNode *lowestCommonAncestorII(ParentTreeNode *root,
ParentTreeNode *A,
ParentTreeNode *B) {
if(root == NULL) return NULL;
int ha = GetHeight(A);
int hb = GetHeight(B);
//assume B is deeper, if not, swap
if(ha > hb) {
swap(A, B);
swap(ha, hb);
}
int diff = hb - ha;
//move B up diff times
for(int i=0; i<diff; i++) {
B = B->parent;
}
while(A && B) {
if(A == B) return A;
A = A->parent;
B = B->parent;
}
return NULL;
}
int GetHeight(ParentTreeNode *node) {
int h = 0;
while(node != NULL) {
h++;
node = node->parent;
}
return h;
}
};