LCA(Lowest Common Ancestor)

주어진 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘

핵심 요소

1. Depth 배열: 각 노드의 깊이(루트에서 해당 노드까지의 거리)를 저장
2. Parent 배열: 각 노드의 부모 노드 정보를 저장

프로세스

1. Depth 및 Parent 계산: 먼저 트리를 순회하면서 각 노드의 깊이와 부모 노드 정보를 저장(DFS나 BFS 이용)
2. LCA 찾기:
   • 두 노드의 깊이가 다를 경우, 깊이가 더 깊은 노드를 그의 부모 노드로 올려서 깊이를 일치시킴
   • 두 노드의 깊이가 같아지면, 두 노드가 같아질 때까지 각 노드를 그 부모 노드로 이동
   • 같아지는 순간의 노드가 LCA

예제

function findLCA(parent, depth, node1, node2) {
    // 먼저 두 노드의 깊이를 같게 맞춥니다.
    while (depth[node1] !== depth[node2]) {
        if (depth[node1] > depth[node2]) {
            node1 = parent[node1];
        } else {
            node2 = parent[node2];
        }
    }

    // 깊이를 맞춘 후, 두 노드가 같아질 때까지 부모 노드로 올라갑니다.
    while (node1 !== node2) {
        node1 = parent[node1];
        node2 = parent[node2];
    }

    return node1; // 또는 node2, 둘은 이 시점에서 같습니다.
}

// 예제 트리에서의 parent와 depth 정보 (노드 번호는 1부터 시작)
const parent = [0, 0, 1, 1, 2, 2, 3, 3];
const depth = [0, 1, 1, 2, 2, 2, 2];

// LCA 찾기
console.log(findLCA(parent, depth, 4, 5));  // 결과: 2
console.log(findLCA(parent, depth, 4, 6));  // 결과: 1