트리 - LCA 알고리즘

LCA 알고리즘은 트리에서 최소 공통 조상을 찾는 알고리즘이다.

공통 조상을 찾기위해서는 트리의 깊이를 이용한다.

1. 루트 노드에서 dfs로 순회하며 전체의 부모노드와 깊이를 구한다.

2. 최소 공통 조상을 두 노드를 입력받는다.

3-1. 만약 두 노드의 깊이가 다르다면, 깊이가 깊은 노드를 해당 노드의 부모 노드로 바꿔준다.

두 노드의 깊이가 같아질때까지 3-1를 반복한다.

3-2. 깊이가 같다면, 두 노드의 값을 비교한다. 두 노드의 값이 다르다면, 두 노드 모두 해당 노드들의 부모 노드로 바꿔준다.

두 노드의 값이 같아질때까지 3-2를 반복한다.

1~3 과정을 통해 최소 공통 조상을 구할 수 있다.