129. Sum Root to Leaf Numbers

題目 / Problem

中文： 給定一棵二元樹的根節點 root，樹上每個節點只包含 0 到 9 的數字。每一條「從根到葉」的路徑都代表一個數字：例如路徑 1 -> 2 -> 3 代表數字 123。請回傳所有「根到葉」數字的總和。測資保證答案能放進 32 位元整數。葉節點是指沒有任何子節點的節點。

English: You are given the root of a binary tree whose nodes each hold a single digit 0–9. Every root-to-leaf path spells out a number (path 1 -> 2 -> 3 = the number 123). Return the sum of all those root-to-leaf numbers. The answer is guaranteed to fit in a 32-bit integer. A leaf is a node with no children.

Constraints: - Number of nodes is in [1, 1000]. - 0 <= Node.val <= 9. - Tree depth will not exceed 10.

Worked example: root = [1,2,3]

      1
     / \
    2   3

Path 1->2 = 12, path 1->3 = 13. Sum = 12 + 13 = 25.

名詞解釋 / Glossary

• 二元樹 / Binary tree: 一種樹狀結構，每個節點最多有兩個子節點，分別叫做左子節點（left）和右子節點（right）。A tree where each node has at most two children, called left and right.
• 葉節點 / Leaf node: 沒有左子節點也沒有右子節點的節點；它是一條路徑的終點。A node with no children — the end of a path.
• 深度優先搜尋 (DFS) / Depth-First Search: 一種走訪策略：先沿著一條路徑一直往下走到底（走到葉節點），再回頭走別的分支。A traversal that dives down one full path to its leaf before backtracking to explore other branches.
• 遞迴 / Recursion: 函式呼叫自己來處理更小的子問題；這裡我們對左右子樹各呼叫一次同樣的函式。A function that calls itself on smaller subproblems — here, once for each subtree.
• 累積值 / Running number (cur): 一個沿路徑往下傳遞的參數，記錄「從根到目前節點所拼出的數字」。A value passed down the path that holds the number spelled out so far from the root to the current node.
• *10 + digit 技巧 / Build-number-by-digit trick: 每往下一層，就把目前的數字乘以 10 再加上新的位數，等同於在數字尾端接上一個新數字（12 → 12*10+3 = 123）。Multiplying by 10 then adding the new digit appends that digit to the right (12 → 123).

思路

最直接的暴力想法是：先找出所有「根到葉」的路徑，把每條路徑上的數字存進一個陣列（例如 [1,2,3]），再把陣列轉成數字 123，最後全部加總。這樣做是對的，但要額外維護路徑陣列、進出時 push/pop，還要做一次「陣列轉數字」的轉換，程式碼囉嗦又容易出錯。關鍵觀察是：我們其實不需要把整條路徑存下來，只需要一個「到目前為止拼出的數字」cur。從根出發時 cur = root.val；每往下走一層到節點 x，新的數字就是 cur * 10 + x.val——因為乘以 10 相當於把原數字往左推一位，空出來的個位再填上新數字。當我們走到葉節點（左右子樹都是空的）時，cur 正好就是這條完整路徑代表的數字，直接把它加進答案即可。用 DFS 遞迴自然地實現這個過程：對每個節點，把更新後的 cur 傳給左子樹與右子樹，兩邊回傳的結果相加就是「以此節點為根、往下所有路徑的總和」。這樣只走訪每個節點一次，不需要額外的路徑陣列。

The brute-force idea is to enumerate every root-to-leaf path, collect its digits into a list like [1,2,3], convert that list to the number 123, and sum them all. That works, but it forces you to maintain a path list with push/pop bookkeeping plus a list-to-number conversion — verbose and error-prone. The key insight is that you never need the whole path, only a single running value cur that holds "the number built so far." Start with cur = root.val; each time you descend to a child x, the new value is cur * 10 + x.val, because multiplying by 10 shifts every existing digit one place left and the new digit slots into the freed units place. When you reach a leaf (both children null), cur is exactly the number for that path, so you add it to the total. A DFS recursion expresses this cleanly: for each node, pass the updated cur down to the left and right subtrees and return the sum of what they report — the total of all paths beneath that node. Each node is visited exactly once, no auxiliary path array needed.

逐步走查 / Walkthrough

Input: root = [1,2,3]. We call dfs(node, cur) where cur is the number built from the root down to (but not including) node's own contribution — actually we fold the node's value in as the first step. Let's trace with cur meaning "value so far including this node."

Final answer: 25. Notice cur starts at 0 at the very top, so the root itself is handled by the same cur*10 + val rule (0*10 + 1 = 1) — no special case for the root.

Solution — C

// 演算法：DFS 遞迴。每往下一層用 cur = cur*10 + val 拼數字，
// 到葉節點時把 cur 加進總和。/ Algorithm: DFS. Build the number with
// cur = cur*10 + val on the way down; at a leaf, cur is that path's number.

/**
 * Definition for a binary tree node.  (由 LeetCode 提供 / provided by LeetCode)
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 輔助遞迴函式：回傳「以 node 為根、目前已拼出 cur」的所有路徑數字總和
// Helper recursion: returns the sum of all path-numbers under `node`,
// given `cur` = number built so far from the real root down to node's parent.
int dfs(struct TreeNode* node, int cur) {
    // 空節點沒有任何路徑，貢獻 0 / A null node contributes nothing.
    if (node == NULL) return 0;

    // 把目前節點的位數接到 cur 尾端 / Append this node's digit to cur.
    // cur*10 讓現有數字往左移一位，再 + node->val 填入個位。
    // cur*10 shifts existing digits left one place, + val fills the units digit.
    cur = cur * 10 + node->val;

    // 葉節點：左右子樹皆為空，cur 就是這條完整路徑的數字。
    // Leaf: both children null, so cur is this path's finished number.
    if (node->left == NULL && node->right == NULL) return cur;

    // 非葉節點：把更新後的 cur 傳給左右子樹，兩邊總和即為答案。
    // Internal node: recurse into both children with the updated cur and add.
    return dfs(node->left, cur) + dfs(node->right, cur);
}

// LeetCode 要求的進入點 / The entry point LeetCode calls.
int sumNumbers(struct TreeNode* root) {
    // 一開始 cur = 0，讓根節點也套用 cur*10+val 的規則（0*10+val = val）。
    // Start cur at 0 so the root uses the same rule (0*10 + val = val).
    return dfs(root, 0);
}

Solution — C++

// 演算法：DFS 遞迴。每往下一層用 cur = cur*10 + val 拼數字，
// 到葉節點時回傳 cur；內部節點回傳左右子樹總和。
// Algorithm: DFS. Build the number with cur = cur*10 + val going down;
// return cur at a leaf, else return the sum from both subtrees.

/**
 * Definition for a binary tree node.  (由 LeetCode 提供 / provided by LeetCode)
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     ...
 * };
 */
class Solution {
public:
    // 主函式 / Public entry point LeetCode calls.
    int sumNumbers(TreeNode* root) {
        // 從 cur = 0 開始，根節點自然套用 0*10+val = val 的規則。
        // Start cur at 0; the root then uses 0*10 + val = val, no special case.
        return dfs(root, 0);
    }

private:
    // 私有輔助遞迴函式 / Private recursive helper.
    // cur 是「從根到 node 父節點」已拼出的數字 / cur = number built down to node's parent.
    int dfs(TreeNode* node, int cur) {
        // 空節點貢獻 0 / A null child contributes nothing.
        if (node == nullptr) return 0;

        // 把本節點的位數接到尾端 / Append this node's digit.
        // *10 把舊數字左移一位，+val 填個位。/ *10 shifts left, +val fills the units place.
        cur = cur * 10 + node->val;

        // 葉節點：cur 即為此路徑的完整數字。/ Leaf: cur is this path's finished number.
        if (node->left == nullptr && node->right == nullptr) return cur;

        // 內部節點：左右子樹各遞迴一次並相加。
        // Internal node: recurse into both subtrees with updated cur and sum them.
        return dfs(node->left, cur) + dfs(node->right, cur);
    }
};

複雜度 / Complexity

• Time: O(n) — 其中 n 是節點數量。DFS 對每個節點剛好走訪一次，每次只做常數次算術運算。n is the number of nodes; DFS visits each node exactly once and does O(1) arithmetic per node, so total work is linear.
• Space: O(h) — 其中 h 是樹的高度（本題 h <= 10）。空間來自遞迴呼叫堆疊，最深同時只有一條根到葉的路徑在堆疊上。h is the tree height (here h <= 10); space is the recursion call stack, which holds at most one root-to-leaf path at a time. 最壞情況（歪斜樹 skewed tree）h = n，最佳情況（平衡樹 balanced tree）h = log n。

Pitfalls & Edge Cases

• 葉節點的判斷 / Correct leaf test: 一定要「左右子樹都為空」才算葉節點。只檢查一邊會在只有單邊子節點的情況下提早加總，答案錯誤。A leaf needs both children null; checking only one side wrongly treats a one-child node as a leaf.
• 不要在每個節點都加 cur / Don't add at every node, only at leaves: 只有走到葉節點才把 cur 計入答案。若在內部節點也加，會重複計算前綴數字。Only leaves contribute; adding cur at internal nodes double-counts prefixes.
• cur 的初始值 / Initialize cur to 0, not the root's value: 從 0 開始能讓根節點也套用同一條 cur*10+val 規則，避免為根寫特例。Starting at 0 lets the root use the same formula, so no special-casing.
• 溢位不用擔心 / Overflow is safe here: 題目保證答案落在 32 位元整數內，深度 <= 10 使單一路徑數字最多 10 位、且總和保證合法，所以 int 足夠。The statement guarantees the answer fits in a 32-bit int, so plain int is fine — no long needed.
• 單一節點的樹 / Single-node tree: 若樹只有根節點（例如 [5]），它本身就是葉節點，直接回傳 5。程式碼透過葉節點分支自然處理。A lone root is itself a leaf; the leaf branch returns its value directly.
• 保證非空 / Root is never null: 約束說節點數 >= 1，但 dfs 仍先檢查 NULL，讓遞迴到不存在的子節點時安全回傳 0。The NULL/nullptr guard also protects recursion into absent children.