題目
#

leetcode 129 - Sum Root to Leaf Numbers (題目說明請點連結)

題目簡述
#

給定一個二元樹，計算從根節點到所有葉子節點的路徑所代表的數字總和。每個路徑代表一個數字，從根節點到葉子節點的數字按順序組成。

範例
#

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation: 根到葉子的路徑 1->2 代表數字 12。根到葉子的路徑 1->3 代表數字 13。因此，總和 = 12 + 13 = 25。

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation: 根到葉子的路徑 4->9->5 代表數字 495。根到葉子的路徑 4->9->1 代表數字 491。根到葉子的路徑 4->0 代表數字 40。因此，總和 = 495 + 491 + 40 = 1026。

___

解題思路
#

這題要求我們計算從根節點到所有葉子節點的路徑所代表的數字總和。每個路徑代表一個數字，從根節點到葉子節點的數字按順序組成。

我們需要遍歷所有從根到葉子的路徑，並累加每個路徑代表的數字。

解法
#

使用 DFS 來解決：

從根節點開始，維護一個當前路徑的數字。
每訪問一個節點，將當前數字乘以10再加上節點值。
當到達葉子節點時，將完整路徑的數字加入總和。
遞歸訪問左右子樹。

完整程式碼
#

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 全局變數，記錄所有路徑數字的總和
    int sum = 0;

    public int sumNumbers(TreeNode root) {
        // 邊界條件：空樹返回 0
        if(root == null){
            return 0;
        }
        // 從根節點開始 DFS，初始數字為 0
        dfs(root, 0);
        return sum;
    }

    /**
     * DFS 遍歷函數
     * @param root 當前節點
     * @param num 當前路徑的數字
     */
    public void dfs(TreeNode root, int num) {
        // 將當前節點的值加入路徑數字中
        num = 10 * num + root.val;

        // 如果到達葉子節點，將完整路徑數字加入總和
        if(root.left == null && root.right == null){
            sum += num;
            return;
        }

        // 遞歸訪問左子樹
        if(root.left != null){
            dfs(root.left, num);
        }
        // 遞歸訪問右子樹
        if(root.right != null){
            dfs(root.right, num);
        }
    }
}