[해커랭크] Binary Search Tree : Lowest Common Ancestor (C++)

문제 링크: www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/problem

Binary Search Tree : Lowest Common Ancestor | HackerRank

1. 주의할 점

- LCA 정석풀이로 풀 수 있지만, BST의 특성을 활용하면 쉽게 풀 수 있다

- LCA, BST에 대해 알고 있어야 한다

 

2. 구현

- BST란? 1개의 Node에 최대 2개의 자식이 존재할 수 있다. 또한, 현재 Node를 기준으로 왼쪽의 Subtree는 자기자신보다 모두 낮은 값을 가지며, 오른쪽 Subtree는 자기자신보다 모두 높은 값을 가진다

- 여기서 왼쪽은 모두 낮고, 오른쪽은 모두 높은 값을 가져야 함에 유의한다

- LCA란 2개의 Node가 자기자신을 포함하여 부모를 타고 올라가며 둘이 최초로 만나는 지점이다

- 위의 말을 해석하면, LCA란 최초로 둘이 Left<->Right Subtree로 갈라지기 시작하는 지점이다. 또한, 2개의 Node중 1개가 LCA가 될 수 있다

- 위 2개의 색(파랑, 빨강)에 유의하여 풀면 된다

//1. 모든 경우를 나누는 풀이
Node *lca(Node *root, int v1,int v2) {
    int small = min(v1,v2);
    int big = max(v1,v2)
    while(root){
		int cv = root->data;
      	if(small < cv && cv < big){     //LCA
      		return root;
      	}
       	else if(cv>big)     //둘다 왼쪽 subtree
            root = root->left;
        else if(cv < small)     //둘다 오른쪽 subtree
            root = root->right;
        else{       //둘중 하나가 Root인 경우
            return root;
        }
    }
    return root;
}

//2. 3가지 경우로 나누는 풀이
Node *lca(Node *root, int v1,int v2) {
    int small = min(v1,v2);
    int big = max(v1,v2)
    while(root){
        int cv = root->data;
        if(cv>big)     //둘다 왼쪽 subtree
        root = root->left;
        else if(cv < small)     //둘다 오른쪽 subtree
        root = root->right;
        else{       //둘중 하나가 Root인 경우 or 처음으로 둘이 갈라진 경우 = LCA
            return root;
        }
    }
    return root;
}