// 演算法：DFS 遞迴。每往下一層用 cur = cur*10 + val 拼數字，
// 到葉節點時把 cur 加進總和。/ Algorithm: DFS. Build the number with
// cur = cur*10 + val on the way down; at a leaf, cur is that path's number.

/**
 * Definition for a binary tree node.  (由 LeetCode 提供 / provided by LeetCode)
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 輔助遞迴函式：回傳「以 node 為根、目前已拼出 cur」的所有路徑數字總和
// Helper recursion: returns the sum of all path-numbers under `node`,
// given `cur` = number built so far from the real root down to node's parent.
int dfs(struct TreeNode* node, int cur) {
    // 空節點沒有任何路徑，貢獻 0 / A null node contributes nothing.
    if (node == NULL) return 0;

    // 把目前節點的位數接到 cur 尾端 / Append this node's digit to cur.
    // cur*10 讓現有數字往左移一位，再 + node->val 填入個位。
    // cur*10 shifts existing digits left one place, + val fills the units digit.
    cur = cur * 10 + node->val;

    // 葉節點：左右子樹皆為空，cur 就是這條完整路徑的數字。
    // Leaf: both children null, so cur is this path's finished number.
    if (node->left == NULL && node->right == NULL) return cur;

    // 非葉節點：把更新後的 cur 傳給左右子樹，兩邊總和即為答案。
    // Internal node: recurse into both children with the updated cur and add.
    return dfs(node->left, cur) + dfs(node->right, cur);
}

// LeetCode 要求的進入點 / The entry point LeetCode calls.
int sumNumbers(struct TreeNode* root) {
    // 一開始 cur = 0，讓根節點也套用 cur*10+val 的規則（0*10+val = val）。
    // Start cur at 0 so the root uses the same rule (0*10 + val = val).
    return dfs(root, 0);
}