코딩 테스트는 소프트웨어 개발자에게 매우 중요한 과정입니다. 특히, 알고리즘 문제는 여러분의 문제 해결 능력을 보여줄 수 있는 좋은 기회입니다. 이번 강좌에서는 트리 구조에서 최소 공통 조상(LCA, Lowest Common Ancestor)을 찾는 문제를 다룰 것입니다.
문제 설명
주어진 이진 트리에서 두 노드 A와 B의 최소 공통 조상(LC)은 노드 A와 B의 조상 중에서 가장 깊은 노드를 의미합니다. 즉, A와 B의 경로를 따라 가장 가까운 공통 조상을 찾아야 합니다.
문제: 이진 트리가 주어지며, 두 노드 A와 B의 값을 입력받습니다. 최소 공통 조상을 반환하는 함수를 작성하세요.
입력
- 이진 트리의 루트 노드 root가 주어진다.
- 노드 A와 노드 B의 값이 주어진다.
출력
- 최소 공통 조상의 노드 값을 반환한다.
제한 사항
- 이진 트리의 노드는 중복되지 않는다.
- 노드는 항상 존재하며, A와 B는 트리에 반드시 포함된다.
알고리즘 접근 방법
최소 공통 조상을 찾기 위해 트리를 탐색할 필요가 있습니다. 깊이 우선 탐색(DFS) 방법을 사용하여 각 노드에 도달할 때까지 재귀적으로 탐색합니다. 각 노드에서 A와 B를 찾는 방법은 다음과 같습니다.
- 루트 노드를 검사하여 A 또는 B와 일치하는지 확인합니다.
- 지금 검사하는 노드가 없으면 null을 반환합니다.
- 좌측 자식과 우측 자식을 재귀적으로 검사하며, 두 자식 호출 결과를 확인합니다.
- 두 자식 호출에서 각각의 결과가 null이 아닐 경우, 현재 노드가 최소 공통 조상입니다.
- 하나의 자식만이 null이 아닐 경우, 그 자식이 최소 공통 조상이 됩니다.