[돌머리] 돌머리를 깨기 위한 간단한 알고리즘 문제 – 공통 선조 찾기

Design an algorithm to find the least common ancestor of two nodes in a Binary tree(Note: Its not a binary search Tree)
Node Structure is given as

Class Node{
int data;
Node leftchild;
Node Rightchild;
}

solution) I just think that if one node notice that there are 2 nodes that we want to find. it is the common ancestor of two nodes. so it's solution is really easy to understand.


int find_node2( Node *node, int value1, int value2 ) {
 int ret = 0;
 if( node->data == value1 || node->data == value2 ) {
 ret++;
 }

if( node->left ) {
 ret += find_node2( node->left, value1, value2 );
 }

if( node->right ) {
 ret += find_node2( node->right, value1, value2 );
 }

if( ret == 2 ){
 printf("this node is common parent: %d(%d,%d)\n",
 node->data, value1, value2);
 }

return ret > 0 ? 1 : 0;
}