[알고리즘] Lowest common ancestor

LCA 의 정의는 다음 페이지에서 확인.

https://en.wikipedia.org/wiki/Lowest_common_ancestor

결론적으로, Tree에서 주어진 2개의 노드에 대해서

가장 가까운 공통 부모를 찾는 문제이다.

내가 제일 먼저 생각해 낸 방식은

각 노드의 부모노드를 쭈욱 나열한다.

그리고, 그 노드의 공통값 중에서 가장 depth 가 높은 것을 선택하는 것이다.

1) depth first 로 search하면서 부모 hashmap 구축

2) 두 노드의 부모 리스트 획득

3) 각 부모 리스트 중 depth가 가장 깊은 것 선정



정답 코드는 다음과 같다.

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    return left == null ? right : right == null ? left : root;
}

이 코드를 이해할 수 있는가?

웬만한 역량가지고는 이 코드를 이해하기 쉽지 않은데, 작성한 사람도 참 대단하다.

마지막 줄을 유심히 보자.

    return left == null ? right : right == null ? left : root;

p와 q노드를 찾아나가는데,

left 가 null이면 right을 반환
left 가 null이 아니면 right이 null이면 left반환
left 가 null 이 아니고 right이 null이 아니면 본인 반환

            1
       2         3
  4        5


위 구조일때, p = 4, q = 5라고 하자.

그럼, 함수가 재귀호출을 하면서 4까지 내려갈 것이다.

4에 왔을 때, root(4) = p 이므로

자기 자신을 반환한다.

그리고 5에 대해서는 root(5) = q이므로

역시 자기 자신을 반환한다.

그럼 node 2에 대해서는 양 옆에서 온 녀석이 둘다 null이 아니므로

자기 자신을 반환한다.

다시 올라가서, node1은 오른쪽에서는 null이 반환될 것이고

왼쪽에서는 2가 반환되었을 것이다.

한쪽만 null이 아니므로 null 이 아닌 2를 반환해서 결국 정답은

node 2가 된다.


한편, 같은 구조에서 p = 4, q = 3 이라고 하자.

그럼, node 1에서 왼쪽으로는 4가 올 것이고, 오른쪽으로는 3이 올 것이다.

그래서 답은 node 1 의 자기 자신인 node 1이 된다.


tree, graph를 공부했고, 재귀함수를 공부했고,
다양한 알고리즘 패턴을 공부했지만 (greedy, divide&conqure 등)

이 문제를 푸는 두 번째 방법은 이해하기 조차 어려웠다.

당연히 솔루션으로 생각조차 못해 냈다.

다른 비슷한 문제가 나왔을 때 적용가능한 공통 원리라는 게 있을까?

일단은 좀 더 케이스 스터디를 늘리는 방법밖에 없을 거 같다.