LCA(Loweast Common Ancestor)
- 최소 공통 조상을 찾는 알고리즘이다.
- 즉 두 노드에서 가장 가까운 공통 조상을 찾는 알고리즘이다
- 다음과 같은 그래프에서 6,9의 최소 공통 조상은 2이다.
접근방법
- 최소 공통 조상을 찾는 방법은 각 노드에서 부모를 타고 올라가서 같은 부모를 찾으면 될 것이다.
- 하지만 이때 양 노드의 Level이 같아야 이러한 방법으로 접근할 수 있다.
결과적으로 각 노드의 부모와 레벨을 알아야한다. 필요한 것은 각 노드의 부모와 레벨, 그리고 트리이다.
즉 각 노드의 부모 노드와 레벨을 저장해야 하는데 DFS를 돌면서 저장할 수 있다.
재귀를 한번씩 돌 때마다 레벨이 1씩 올리면서 저장하고 부모노드 또한 저장이 가능하다.