LeetCode 129 求根節點到葉節點數字之和：DFS 遞歸與迭代雙解法

題目大意

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

遞歸 DFS（最直觀）

int sumNumbers(TreeNode* root) {
    function dfs = [&](TreeNode* node, int cur) {
        if (!node) return 0;
        cur = cur * 10 + node->val;
        if (!node->left && !node->right) return cur;
        return dfs(node->left, cur) + dfs(node->right, cur);
    };
    return dfs(root, 0);
}

時間 O(n)，空間 O(h)（遞歸棧，h 為樹高）。

迭代 DFS（顯式棧，避免棧溢出）

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

BFS 層序遍歷（同樣可行）

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

關鍵點總結

• 路徑數字構建：new_val = old_val * 10 + node->val。
• 葉節點判斷：!left && !right。
• 空樹返回 0。
• 數值範圍：題目保證 32 位有符號整數足夠，實際可用 long long 防溢出。

進階變體

• 路徑總和 II/III：收集所有路徑 / 求和等於目標值的路徑數。
• 二叉樹最大路徑和：路徑可不經過根，需後序遍歷維護最大值。