🌳 初学者友好指南 '根到叶的二进制数之和' - Problem 1022 (C++, Python, JavaScript)

Source: Dev.to

问题概述

二叉树是层次结构数据的核心，掌握如何遍历它们是每位开发者的基础技能。
在本题中，从根到叶子的每条路径都代表一个二进制数。任务是计算所有这些数的和。

方法

核心思路是在遍历树的过程中构建二进制数：

• 向下移动一层时，将当前值左移一位（乘以 2），再加上节点的位。
• 使用深度优先搜索（DFS）遍历每条分支。
• 通过递归调用将“当前值”向下传递。
• 当到达叶子节点时，将累计的值加入总和。

关键概念

• 前序遍历 – 在子节点之前处理当前节点。
• 累加器模式 – 将当前路径值作为参数传递，避免使用全局状态。
• 位操作 – val = (val * 2) + bit 将位序列转换为十进制表示。

示例

考虑一棵树，根节点为 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）的熟练程度。
• 二进制数构造和位操作的理解。

类似的逻辑出现在实际系统中，例如用于数据压缩的 Huffman 编码和 IP 路由表（Trie），这些场景中二进制前缀存储在类似树的结构中以实现快速查找。掌握此模式为更复杂的系统设计挑战奠定坚实基础。