LeetCode 129 Sum Root to Leaf Numbers：二叉樹路徑數字求和

LeetCode 129 經典題目：給定只含數字 0-9 的二叉樹，每條根到葉路徑代表一個數字，求所有路徑數字之和。

題目範例

    1
   / \
  2   3

• 路徑 1→2：數字 12
• 路徑 1→3：數字 13
• 總和 = 12 + 13 = 25

解法：深度優先搜尋 (DFS) + 回溯

class Solution {
private:
    void dfs(TreeNode* root, int& sum, int& pathVal) {
        if (!root) return;
        
        // 更新路徑數值：原值 * 10 + 當前節點值
        pathVal = pathVal * 10 + root->val;
        
        // 葉節點：累加到總和
        if (!root->left && !root->right) {
            sum += pathVal;
        }
        
        // 遞歸左右子樹
        if (root->left)  dfs(root->left,  sum, pathVal);
        if (root->right) dfs(root->right, sum, pathVal);
        
        // 回溯：恢復路徑數值 (減去當前節點貢獻)
        pathVal = (pathVal - root->val) / 10;
    }
    
public:
    int sumNumbers(TreeNode* root) {
        int sum = 0, pathVal = 0;
        dfs(root, sum, pathVal);
        return sum;
    }
};

核心邏輯圖解

路徑 1→2→3 的數值構建過程：
pathVal = 0
  → 節點 1: 0*10+1 = 1
    → 節點 2: 1*10+2 = 12 (葉節點，sum += 12)
    → 回溯: (12-2)/10 = 1
    → 節點 3: 1*10+3 = 13 (葉節點，sum += 13)
    → 回溯: (13-3)/10 = 1
  → 回溯: (1-1)/10 = 0
最終 sum = 25

複雜度分析

關鍵技巧總結

• 路徑數值累積：利用十進制位移特性 val = val*10 + digit
• 回溯恢復：遞歸返回前撤銷當前節點影響 val = (val - digit)/10
• 引用參數：sum 累加總和，pathVal 維護當前路徑值
• 葉節點判斷：!left && !right 確保只在完整路徑結算

變體擴展

• 求最大/最小路徑數字
• 返回所有路徑數字列表
• 路徑數字模運算 (大數處理)
• 非遞歸實作 (顯式棧模擬)