題目描述

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

例：

    1
   / \
  2   3

路徑：12 + 13 = 25。

遞歸 DFS 解法

遞歸參數：當前節點、累積值引用、結果引用。到葉節點時將累積值加入結果。回溯時恢復累積值。

代碼實現

#include 
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
    void dfs(TreeNode* root, int& result, int& cur) {
        if (!root) return;
        cur = cur * 10 + root->val; // 更新累積值
        if (!root->left && !root->right) // 葉節點
            result += cur;
        if (root->left) dfs(root->left, result, cur);
        if (root->right) dfs(root->right, result, cur);
        cur = (cur - root->val) / 10; // 回溯恢復
    }
public:
    int sumNumbers(TreeNode* root) {
        int result = 0, cur = 0;
        dfs(root, result, cur);
        return result;
    }
};

迭代版（棧模擬）

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

複雜度

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

關鍵點

• 累積值更新：cur = cur * 10 + val
• 葉節點判斷：!left && !right
• 回溯恢復：cur = (cur - val) / 10（整數除法）
• 迭代版無需回溯，狀態封裝在棧中