🌳 초보자용 가이드 'Root To Leaf Binary Numbers의 합' - Problem 1022 (C++, Python, JavaScript)

Source: Dev.to

문제 개요

이진 트리는 계층형 데이터 구조의 핵심이며, 트리를 순회하는 방법을 이해하는 것은 모든 개발자에게 기본적인 기술입니다.
이 문제에서는 루트에서 리프까지의 각 경로가 하나의 이진수를 나타냅니다. 모든 이러한 이진수의 합을 구하는 것이 목표입니다.

접근 방법

트리를 순회하면서 이진수를 만들어 나가는 것이 핵심 아이디어입니다:

• 한 레벨 아래로 내려갈 때 현재 값을 왼쪽으로 한 비트 이동( *2 )하고 노드의 비트를 더합니다.
• 깊이 우선 탐색(DFS)을 사용해 각 가지를 탐색합니다.
• “현재 값”을 재귀 호출의 인자로 전달합니다.
• 리프 노드에 도달하면 누적된 값을 전체 합에 더합니다.

핵심 개념

• 전위 순회(Pre‑order Traversal) – 현재 노드를 자식보다 먼저 처리합니다.
• 누산기 패턴(Accumulator Pattern) – 현재 경로 값을 매개변수로 전달해 전역 상태를 사용하지 않습니다.
• 비트 연산(Bit Manipulation) – val = (val * 2) + bit 은 비트 시퀀스를 10진수로 변환합니다.

예시

루트가 1이고 리프가 만드는 경로가 (1,0,0), (1,0,1), (1,1,0), (1,1,1) 인 트리를 생각해 봅시다.

1. 루트(1)에서 시작: 현재 값 = 1.
2. 왼쪽 자식(0)으로 이동: 1 × 2 + 0 = 2.
3. 왼쪽 리프(0): 2 × 2 + 0 = 4 → 4를 더함.
4. 오른쪽 리프(1): 2 × 2 + 1 = 5 → 5를 더함.
5. 오른쪽 서브트리에서도 동일하게 진행 → 값은 6과 7.

전체 합 = 4 + 5 + 6 + 7 = 22.

C++ 풀이

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        int totalSum = 0;
        dfs(root, 0, totalSum);
        return totalSum;
    }

private:
    void dfs(TreeNode* node, int currentVal, int& totalSum) {
        if (node == nullptr) return;

        // Shift left (multiply by 2) and add the current node's bit
        currentVal = currentVal * 2 + node->val;

        // If it's a leaf node, add the accumulated value to the total
        if (node->left == nullptr && node->right == nullptr) {
            totalSum += currentVal;
            return;
        }

        dfs(node->left, currentVal, totalSum);
        dfs(node->right, currentVal, totalSum);
    }
};

Python 풀이

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        self.total_sum = 0

        def dfs(node, current_val):
            if not node:
                return

            # Binary shift logic: current_val * 2 is equivalent to current_val  {
        if (!node) return;

        // Build the number as we descend
        currentVal = (currentVal * 2) + node.val;

        // If both children are null, we are at a leaf
        if (!node.left && !node.right) {
            totalSum += currentVal;
            return;
        }

        dfs(node.left, currentVal);
        dfs(node.right, currentVal);
    };

    dfs(root, 0);
    return totalSum;
};

왜 이 문제가 중요한가

이 “Easy” 등급 문제는 기술 면접에서 인기가 높은데, 그 이유는 다음 두 가지를 동시에 평가하기 때문입니다:

• 트리 재귀(DFS) 구현 능력.
• 이진수 구성 및 비트 연산에 대한 이해.

유사한 로직은 데이터 압축을 위한 허프만 코딩이나 IP 라우팅 테이블(트라이)과 같이 이진 프리픽스를 트리 형태로 저장해 빠르게 조회하는 실제 시스템에서도 나타납니다. 이 패턴을 마스터하면 보다 복잡한 시스템 설계 과제에 대한 탄탄한 기반을 다질 수 있습니다.