🌠초보자 친화 가이드 ‘가장 깊은 노드들을 모두 포함하는 가장 작은 서브트리’ – LeetCode 865 (C++, Python, JavaScript)

Source: Dev.to

문제 요약

주어지는 것:

• root 이진 트리의 루트.
• 다양한 레벨에 있는 노드들 중, “가장 깊은” 노드는 루트에서 가장 멀리 떨어진 노드이다.

목표:

• 그 가장 깊은 노드들을 모두 포함하는 가장 작은 서브트리를 찾는다. 가장 깊은 노드가 하나뿐이라면 그 노드 자체가 답이다.

직관

이 문제를 해결하려면 각 노드에 대해 두 가지를 알아야 합니다: 자손들의 깊이가 얼마나 깊은가? 그리고 그들의 공통 조상이 어떤 노드인가?

재귀적인 깊이 우선 탐색(DFS) 방식을 사용합니다. 단일 값을 반환하는 대신, 함수는 한 쌍을 반환합니다: 해당 서브트리에서 도달한 가장 깊은 레벨과 최소 공통 조상 (LCA)의 후보 노드.

• 기본 경우: 노드가 null이면 깊이는 0이고 LCA가 없습니다.
• 재귀 단계: 왼쪽과 오른쪽 자식의 최대 깊이를 조회합니다.
  • 왼쪽이 더 깊으면, 가장 깊은 노드들은 왼쪽 서브트리 안에만 존재하므로 왼쪽 결과를 위로 전달합니다.
  • 오른쪽이 더 깊으면, 가장 깊은 노드들은 오른쪽 서브트리 안에만 존재하므로 오른쪽 결과를 위로 전달합니다.
  • 깊이가 같으면, 가장 깊은 노드들이 왼쪽과 오른쪽 가지에 나뉘어 있으므로 현재 노드가 이를 연결하는 가장 작은 서브트리가 됩니다.

코드 블록

C++

struct Result {
    TreeNode* lca;
    int depth;
};

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).lca;
    }

private:
    Result dfs(TreeNode* root) {
        if (root == nullptr) return {nullptr, 0};

        Result left = dfs(root->left);
        Result right = dfs(root->right);

        // If one side is deeper, the deepest nodes are exclusively there
        if (left.depth > right.depth) {
            return {left.lca, left.depth + 1};
        }
        if (left.depth  // truncated line from original source

Python

class Solution:
    def subtreeWithAllDeepest(self, root):
        def dfs(node):
            if not node:
                return None, 0

            left_lca, left_depth = dfs(node.left)
            right_lca, right_depth = dfs(node.right)

            if left_depth > right_depth:
                return left_lca, left_depth + 1
            if right_depth > left_depth:
                return right_lca, right_depth + 1

            # If depths are equal, current node is the LCA
            return node, left_depth + 1

        return dfs(root)[0]

JavaScript

var subtreeWithAllDeepest = function(root) {
    const dfs = (node) => {
        if (!node) return { lca: null, depth: 0 };

        const left = dfs(node.left);
        const right = dfs(node.right);

        if (left.depth > right.depth) {
            return { lca: left.lca, depth: left.depth + 1 };
        }
        if (right.depth > left.depth) {
            return { lca: right.lca, depth: right.depth + 1 };
        }

        // If depths are equal, this node is the common ancestor
        return { lca: node, depth: left.depth + 1 };
    };

    return dfs(root).lca;
};

핵심 요점

• Post‑order Traversal: 자식 노드를 부모보다 먼저 처리하여 전체 서브트리 정보를 기반으로 결정을 내릴 수 있습니다.
• Multiple Return Values: 노드와 깊이 두 값을 반환함으로써 중복된 탐색을 피하고 알고리즘을 효율적으로 유지합니다.
• LCA Logic: 이 문제는 고전적인 최소 공통 조상(LCA) 문제의 변형으로, “대상”이 특정 값이 아니라 깊이에 따라 동적으로 정의됩니다.

최종 생각

이 문제는 재귀와 복잡한 반환 타입을 다루는 능력을 테스트하기 때문에 기술 면접에서 인기가 많습니다. 실제로는 논리가 데이터베이스 계층 구조에서 “가장 구체적인 공통 카테고리”를 찾거나 복잡한 의존성 트리에서 가장 작은 공유 구성 요소를 식별하는 것과 유사합니다. 계층형 데이터와 작업하는 모든 엔지니어에게 이 하향식 정보 흐름을 마스터하는 것이 필수적입니다.