두 노드의 공통 조상 중에 가장 가까운 조상 찾기
⭐️ 필수 기록
- tree 저장: 인접리스트(양방향 리스트)
- 각 노드의 부모 저장: 조상이 아니라 ⭐️직계 부모⭐️
- 각 노드의 트리 계층(
depth
) 저장 ➡️ 루트 노드 depth: 0
- 방문한 노드 기록
1. 각 노드의 부모와 깊이 저장하기: DFS
⭐️ 루트노드부터 시작해서 리프노드까지 현재 노드와 연결된 노드 중에 자식 노드의 부모 노드를 기록해주기
- 연결된 노드 중에 부모와 자식을 구분하기 위해 방문한 노드는 visit 처리해주기 ➡️ 루트노드부터 탐색하기 때문에 이미 방문한 노드는 현재 노드의 부모이고 아직 방문하지 않은 노드는 자식 노드가 됨
- 자식 노드로 이동할 때마다 tree의 깊이가 깊어지므로
depth
도 늘려주기
2. 최소 공통 조상 찾기: DFS
- 두 노드가 동일해질 때까지 반복: 두 노드가 같으면 현재 노드가 공통 조상 노드
- 두 노드의
depth
를 비교하여 depth
가 같으면 현재 계층에서는 공통 조상이 아니라는 것이므로 두 노드의 부모 계층에서 탐색하도록 넘겨주기
- 두 노드의
depth
가 다르다면 계층이 깊은 노드의 부모와 다른 노드를 비교하도록 넘겨서 depth
맞춰주기
⭐️ 예시 code