// 演算法：後序 DFS。gain(node) 回傳「從 node 只往下走一條直線」的最大和；
// 同時用 node.val + 左貢獻 + 右貢獻 更新全域最大 best。負貢獻用 0 取代。
// Algorithm: post-order DFS. gain(node) returns the best straight-down sum from node;
// meanwhile we update a shared best with node.val + left + right. Negative gains clamped to 0.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 小工具：回傳兩個 int 中較大者 / helper: return the larger of two ints
static int maxInt(int a, int b) {
    return a > b ? a : b;   // 三元運算子：條件 ? 真時的值 : 假時的值 / ternary: cond ? if-true : if-false
}

// 遞迴核心。best 用指標傳入，讓所有呼叫共用同一個變數。
// Recursive core. best is passed by pointer so every call shares the same variable.
static int gain(struct TreeNode* node, int* best) {
    if (node == NULL) return 0;   // 空節點沒有貢獻，回傳 0 / empty node contributes nothing

    // 遞迴算出左右子的向下貢獻 / recurse to get each child's downward gain
    int left = gain(node->left, best);    // node->left 是「取結構指標的成員」/ node->left dereferences the pointer's field
    int right = gain(node->right, best);

    // 若貢獻為負就丟掉（當成 0），因為加上它只會讓路徑更小
    // If a gain is negative, drop it (use 0) — adding it would only shrink the path
    int leftClamped = maxInt(0, left);
    int rightClamped = maxInt(0, right);

    // 以 node 為「最高點/轉彎點」的完整路徑，可同時吃左右兩邊
    // A path bending at node may take BOTH sides at once
    int through = node->val + leftClamped + rightClamped;

    // 用這個候選值更新全域最大 / update the shared best with this candidate
    if (through > *best) *best = through;   // *best 解指標讀寫共用變數 / *best dereferences to read/write the shared value

    // 回傳給父節點時只能選一邊（路徑不能分岔）
    // When returning upward we may keep only ONE side (a path can't fork)
    return node->val + maxInt(leftClamped, rightClamped);
}

int maxPathSum(struct TreeNode* root) {
    // 初始化為最小的 int，因為答案可能是負數（例如整棵樹只有一個 -3）
    // Start at INT_MIN because the answer can be negative (e.g. a lone node with value -3)
    int best = -2147483648;   // INT_MIN
    gain(root, &best);        // &best 取位址，把「共用變數」交給遞迴 / &best passes the variable's address in
    return best;
}