자바스크립트 코딩테스트 강좌, 최소 공통 조상 구하기 2

문제 설명

이 문제는 두 노드의 최소 공통 조상(LCA, Lowest Common Ancestor)을 찾는 문제입니다.
주어진 이진 트리에서 두 개의 노드가 있을 때, 이 두 노드의 공통 조상을 찾는 것입니다.

입력 형식

  • 이진 트리의 루트 노드가 주어집니다.
  • 두 개의 노드 값이 주어집니다.

출력 형식

  • 주어진 두 노드의 최소 공통 조상의 값이나, 없는 경우에는 -1을 출력합니다.

문제 예시

    입력:
        1
       / \
      2   3
     / \
    4   5

    노드 4와 5의 LCA는 2 입니다.
  
    입력:
        1
       / \
      2   3
     / \
    4   5

    노드 4와 3의 LCA는 1 입니다.

    입력:
        1
       / \
      2   3
     / \
    4   5

    노드 6과 7의 LCA는 -1입니다.

문제 풀이

이 문제를 해결하기 위해 다음과 같은 단계로 접근합니다:

  1. 이진 트리 구조 정의:
    먼저, 트리의 구조를 나타내기 위해 노드 클래스를 정의합니다. 이 클래스는 노드의 값을 갖고,
    왼쪽 및 오른쪽 자식 노드를 참조하는 속성을 가집니다.
  2. 재귀적 접근:
    최소 공통 조상을 찾기 위해, 트리를 재귀적으로 탐색합니다.
    현재 노드가 ${p} 또는 ${q}에 해당되면, 현재 노드를 반환합니다.
  3. 좌우 서브트리 확인:
    왼쪽 서브트리 및 오른쪽 서브트리에서 각각 LCA를 찾고, 두 결과가 모두 존재하는 경우
    현재 노드가 LCA입니다.
  4. 결과 반환:
    두 노드가 발견된 경우 현재 노드를 반환하고, 그렇지 않은 경우 null을 반환합니다.

자바스크립트 코드 구현


// 이진 트리 노드 클래스 정의
class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 최소 공통 조상 찾기 함수
function findLCA(root, p, q) {
    // 베이스 케이스: 현재 노드가 null일 경우
    if (root === null) {
        return null;
    }
    
    // 만약 현재 노드가 p 혹은 q일 경우 현재 노드를 반환
    if (root.value === p || root.value === q) {
        return root;
    }
    
    // 좌측과 우측 서브트리에서 LCA 찾기
    const leftLCA = findLCA(root.left, p, q);
    const rightLCA = findLCA(root.right, p, q);
    
    // 만약 왼쪽과 오른쪽 모두에서 결과가 존재할 경우 현재 노드가 LCA
    if (leftLCA && rightLCA) {
        return root;
    }
    
    // 하나의 서브트리에서만 LCA를 찾으면 그 결과를 반환
    return leftLCA !== null ? leftLCA : rightLCA;
}

// 사용 예시
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

const node1 = 4;
const node2 = 5;
const lca = findLCA(root, node1, node2);
console.log(lca ? lca.value : -1); // 결과: 2

결론

최소 공통 조상 찾기는 이진 트리에서 중요한 탐색 문제입니다.
다양한 트리 구조와 노드에 대해 재귀적 접근을 통해 효율적인 방법으로 문제를 해결할 수 있습니다.
이 방법은 여러 가지 상황에서 유용하게 사용될 수 있으며,
재귀적 사고와 트리 탐색 이해에 큰 도움을 줄 것입니다.

추가 과제

아래의 추가 과제를 풀어보세요!

  • 주어진 노드가 존재하지 않는 경우에 대해 처리하는 로직을 추가하세요.
  • 이진 탐색 트리에서 LCA를 찾는 최적화된 방법을 연구하고 구현해보세요.
  • 다양한 트리 구조를 시각화할 수 있는 함수도 구현해보세요.

참고 자료