LeetCode 129 Sum Root to Leaf Numbers：DFS 累積路徑數值求和

題目回顧

給定一棵二叉樹，節點值為 0-9 數字。每條從根到葉的路徑代表一個數字（如 1→2→3 代表 123）。求所有根到葉路徑數字之和。

例：1 / \ 2 3 → 路徑 12 和 13，和 = 25。

核心思路：DFS 遞歸累積

遞歸函數參數：當前節點 node、從根到父節點累積的數值 sum。
當前節點數值 = sum * 10 + node.val。
若為葉節點，返回該值；否則返回左右子樹遞歸結果之和。

C++ 代碼

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }
    
private:
    int dfs(TreeNode* node, int sum) {
        if (!node) return 0;
        sum = sum * 10 + node->val;
        if (!node->left && !node->right) // 葉節點
            return sum;
        return dfs(node->left, sum) + dfs(node->right, sum);
    }
};

Python 代碼

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node, cur):
            if not node: return 0
            cur = cur * 10 + node.val
            if not node.left and not node.right:
                return cur
            return dfs(node.left, cur) + dfs(node.right, cur)
        return dfs(root, 0)

迭代法（棧模擬）

int sumNumbers(TreeNode* root) {
    if (!root) return 0;
    int ans = 0;
    stack> st;
    st.emplace(root, root->val);
    while (!st.empty()) {
        auto [node, val] = st.top(); st.pop();
        if (!node->left && !node->right) ans += val;
        if (node->right) st.emplace(node->right, val * 10 + node->right->val);
        if (node->left) st.emplace(node->left, val * 10 + node->left->val);
    }
    return ans;
}

複雜度

• 時間：O(n)，每個節點訪問一次
• 空間：O(h) 遞歸棧/棧，h 為樹高，最壞 O(n)

測試用例

// 輔助構建樹
TreeNode* build(vector vals) { /* 層序構建略 */ }

// 測試
Solution s;
assert s.sumNumbers(build({1,2,3})) == 25;       // 12+13
assert s.sumNumbers(build({4,9,0,5,1})) == 1026; // 495+491+40
assert s.sumNumbers(nullptr) == 0;