[C++] LCA: 최소공통조상 알고리즘

두 노드의 공통 조상 중에 가장 가까운 조상 찾기

⭐️ 필수 기록

1. tree 저장: 인접리스트(양방향 리스트)
2. 각 노드의 부모 저장: 조상이 아니라 ⭐️직계 부모⭐️
3. 각 노드의 트리 계층(depth) 저장 ➡️ 루트 노드 depth: 0
4. 방문한 노드 기록

1. 각 노드의 부모와 깊이 저장하기: DFS

⭐️ 루트노드부터 시작해서 리프노드까지 현재 노드와 연결된 노드 중에 자식 노드의 부모 노드를 기록해주기

1. 연결된 노드 중에 부모와 자식을 구분하기 위해 방문한 노드는 visit 처리해주기 ➡️ 루트노드부터 탐색하기 때문에 이미 방문한 노드는 현재 노드의 부모이고 아직 방문하지 않은 노드는 자식 노드가 됨
2. 자식 노드로 이동할 때마다 tree의 깊이가 깊어지므로 depth 도 늘려주기

2. 최소 공통 조상 찾기: DFS

1. 두 노드가 동일해질 때까지 반복: 두 노드가 같으면 현재 노드가 공통 조상 노드
2. 두 노드의 depth 를 비교하여 depth 가 같으면 현재 계층에서는 공통 조상이 아니라는 것이므로 두 노드의 부모 계층에서 탐색하도록 넘겨주기
3. 두 노드의 depth 가 다르다면 계층이 깊은 노드의 부모와 다른 노드를 비교하도록 넘겨서 depth 맞춰주기

⭐️ 예시 code