[HackerRank] Tree: Lowest Common Ancestor

Binary Search Tree : Lowest Common Ancestor | HackerRank

Binary Search Tree : Lowest Common Ancestor | HackerRank

 

<문제>

input: 첫번째 줄에는 tree의 원소 개수를 입력하고, 두번재 줄에는 전체 tree를 크기 순서대로 입력받는다. 마지막 줄에 v1, v2에 저장할 트리 내 두 값을 입력한다. 

output: 입력받은 v1, v2의 공통 ancestor 중에서 가장 아래에 있는 것을 리턴한다.

 

<코드>

struct node *lca( struct node *root, int v1, int v2 ) {
    while (root) {
        if (v1 < root->data && v2 < root->data)
            root = root->left;
        else if (v1 > root->data && v2 > root->data)
            root = root->right;
        else
            return root;
    }     
    return root;
}

<풀이>

먼저 root에 있는 값과 각자 비교해서, v1이랑 v2가 모두 root-> data보다 작으면 모두 root의 왼쪽에 존재하기 때문에 root를 더 낮은 위치에 존재하는 root->left가 가리키는 노드로 옮기게 하였다. 또는 모두 root-> data보다 크면 둘 다 root보다 오른쪽에 위치하니 root->right가 가리키는 노드로 root를 옮긴다. 아닌 경우에 그대로 root를 리턴하면 문제가 풀린다.

 

<실행결과>