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

題目描述

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

遞歸解法一：回傳值累加

遞歸函數 `dfs(node, curSum)` 返回以 node 為根的子樹所有路徑數字和。`curSum` 為從根到父節點構成的數字。

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    
    private int dfs(TreeNode node, int curSum) {
        if (node == null) return 0;
        curSum = curSum * 10 + node.val;
        if (node.left == null && node.right == null) {
            return curSum; // 葉節點，返回當前數字
        }
        return dfs(node.left, curSum) + dfs(node.right, curSum);
    }
}

遞歸解法二：全局變量累加

遍歷到葉節點時將當前數字加到全局答案。

class Solution {
    int total = 0;
    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return total;
    }
    void dfs(TreeNode node, int curSum) {
        if (node == null) return;
        curSum = curSum * 10 + node.val;
        if (node.left == null && node.right == null) {
            total += curSum;
            return;
        }
        dfs(node.left, curSum);
        dfs(node.right, curSum);
    }
}

迭代解法：棧模擬 DFS

public int sumNumbers(TreeNode root) {
    if (root == null) return 0;
    int sum = 0;
    Deque nodeStack = new ArrayDeque<>();
    Deque numStack = new ArrayDeque<>();
    nodeStack.push(root);
    numStack.push(root.val);
    while (!nodeStack.isEmpty()) {
        TreeNode node = nodeStack.pop();
        int cur = numStack.pop();
        if (node.left == null && node.right == null) sum += cur;
        if (node.right != null) {
            nodeStack.push(node.right);
            numStack.push(cur * 10 + node.right.val);
        }
        if (node.left != null) {
            nodeStack.push(node.left);
            numStack.push(cur * 10 + node.left.val);
        }
    }
    return sum;
}

複雜度分析

• 時間：O(N)，每個節點訪問一次。
• 空間：O(H) 遞歸棧/棧深度，H 為樹高。最壞 O(N)，平衡樹 O(log N)。