// 演算法：DFS 遞迴。每往下一層用 cur = cur*10 + val 拼數字，
// 到葉節點時回傳 cur；內部節點回傳左右子樹總和。
// Algorithm: DFS. Build the number with cur = cur*10 + val going down;
// return cur at a leaf, else return the sum from both subtrees.

/**
 * Definition for a binary tree node.  (由 LeetCode 提供 / provided by LeetCode)
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     ...
 * };
 */
class Solution {
public:
    // 主函式 / Public entry point LeetCode calls.
    int sumNumbers(TreeNode* root) {
        // 從 cur = 0 開始，根節點自然套用 0*10+val = val 的規則。
        // Start cur at 0; the root then uses 0*10 + val = val, no special case.
        return dfs(root, 0);
    }

private:
    // 私有輔助遞迴函式 / Private recursive helper.
    // cur 是「從根到 node 父節點」已拼出的數字 / cur = number built down to node's parent.
    int dfs(TreeNode* node, int cur) {
        // 空節點貢獻 0 / A null child contributes nothing.
        if (node == nullptr) return 0;

        // 把本節點的位數接到尾端 / Append this node's digit.
        // *10 把舊數字左移一位，+val 填個位。/ *10 shifts left, +val fills the units place.
        cur = cur * 10 + node->val;

        // 葉節點：cur 即為此路徑的完整數字。/ Leaf: cur is this path's finished number.
        if (node->left == nullptr && node->right == nullptr) return cur;

        // 內部節點：左右子樹各遞迴一次並相加。
        // Internal node: recurse into both subtrees with updated cur and sum them.
        return dfs(node->left, cur) + dfs(node->right, cur);
    }
};