Jeff
BAN USERIt seems that we could use post-order traversal of the binary tree to solve the problem. A c++ solution could be like below:
Node *find_lowest_common_ancestor(N ode * root, Node *node1, Node *node2, int &flag) {
if (node1 == node2) {
return node1;
}
if (root == NULL) {
flag = 0;
return NULL;
}
else if (root == node1) {
flag = 1;
return NULL;
}
else if (root == node2) {
flag = 2;
return NULL;
}
int flag1, flag2;
Node *retNode1 = find_lowest_common_ancestor(root->left, flag1);
if (retNode1 != NULL) {
return retNode1;
}
Node *retNode2 = find_lowest_common_ancestor(root->right, flag2);
if (retNode2 != NULL) {
return retNode2;
}
if (flag1 == 1 && flag2 == 2 || flag1 == 2 && flag2 == 1) {
return root;
}
flag = flag1 + flag2;
return NULL;
}
We may use randomized divide and conquer, the time complexity of which should be O(n).
- Jeff September 10, 2012