최소 공통 조상. [3584]

[1. 문제 설명]

root 가 있는 tree 가 입력으로 주어질 때,

Nearest Common Ancestor 는 아래와 같이 정의 된다.

(Lowest Common Ancestor)

• 두 노드의 가장 가까운 공통 조상
• 두 노드를 모두 자식(자손) 으로 가지면서, 깊이가 가장 깊은 노드

최대 10,000 개의 노드가 존재하는 트리가 입력으로 주어지고,

임의의 두 노드가 주어질 때

최소공통조상을 찾는다.

---

[2. 풀이 접근]

A. root 를 찾는다.

• 입력에서 edge 는 부모-자식 관계를 의미한다.
• root 의 부모는 보통 자기 자신으로 정의되니,
• 모든 노드에 대해서 부모가 자기자신인 노드를 찾도록 한다.

B. 각 노드의 높이를 구한다.

• A 단계에서 root 를 찾았으므로,
• root 를 시작으로 dfs 를 수행한다.
• 각 재귀 호출마다, (현재 높이+1) 을 전달하도록 한다.

C. 두 노드의 높이가 일치하지 않는 경우, 같은 레벨로 맞추도록 한다.

• 두 노드의 높이가 같지 않는 경우, 공통 조상 탐색 시 문제가 발생한다.
  => 매 루프마다 바로 위 부모로 올라가게 되는데, 높이가 같지 않는 다면 root 에서 만나게 되기 때문이다.
  => ex) 11 과 12 에서 매 루프마다 위로 올라가면 결국 root 에서만 만나게 된다.

D. 매 루프 마다 위로 올라간다.

• 두 노드가 같아지는 순간 종료하도록 한다.

 

시간복잡도

단계 A> O(n)

단계 B> O(n)

단계 C> O(n) 

==> 트리가 skewed 된 경우를 고려하면...

 

총 시간복잡도 => O(Tn)

---

[3. 코드]