124. Binary Tree Maximum Path Sum

題目 / Problem

中文：二元樹中的「路徑」是一串節點，其中每對相鄰節點之間都有一條邊相連。同一個節點在路徑中最多只能出現一次。注意路徑不一定要經過根節點。一條路徑的「路徑和」就是路徑上所有節點值的總和。給定二元樹的根節點 root，請回傳「任意一條非空路徑」所能得到的最大路徑和。

English: A path in a binary tree is a sequence of nodes where every adjacent pair is joined by an edge. Each node may appear at most once, and the path does not have to go through the root. The path sum is the total of the values on the path. Given the tree's root, return the maximum path sum over all non-empty paths.

Constraints / 限制 - 節點數量 / number of nodes: [1, 3 * 10^4] - 節點值 / node value: -1000 <= Node.val <= 1000

Worked example / 範例 Input: root = [-10,9,20,null,null,15,7]

      -10
      /  \
     9    20
         /  \
        15    7

Output: 42. 最佳路徑是 15 -> 20 -> 7，總和為 15 + 20 + 7 = 42。The best path is 15 -> 20 -> 7, summing to 42. Note it never touches the root -10.

名詞解釋 / Glossary

• binary tree / 二元樹：每個節點最多有兩個子節點（左、右）的樹狀結構 / A tree where each node has at most two children (left and right).
• path / 路徑：一串用邊相連的節點；在這題裡它可以「轉彎」——從左子樹上來、經過某節點、再下去右子樹 / A chain of edge-connected nodes; here it may "bend" — come up from the left subtree, pass through a node, then go down the right subtree.
• DFS (depth-first search) / 深度優先搜尋：一種遍歷方式，先一路往下走到底，再回頭處理其他分支；通常用遞迴實作 / A traversal that dives all the way down one branch before backtracking; usually written with recursion.
• recursion / 遞迴：函式呼叫自己來處理更小的子問題（這裡是左右子樹）/ A function calling itself on smaller subproblems (here, the left and right subtrees).
• downward gain / 向下延伸的最大貢獻：從某節點「只能往下走一條直線」所能拿到的最大和；它不可以同時包含左右兩邊 / The largest sum obtainable starting at a node and going straight down one side — it cannot include both children at once.
• global variable / 全域變數（此處用指標傳遞）：一個在所有遞迴呼叫間共用、用來記錄目前看過的最大答案的變數 / A single value shared across all recursive calls that remembers the best answer seen so far.

思路

暴力法會是：枚舉每一對節點當作路徑的兩端，計算它們之間唯一路徑的和，取最大值。但一棵有 n 個節點的樹有 O(n^2) 對節點，每次求路徑和又要走一遍，總共可能到 O(n^3)，在 n = 3*10^4 時完全跑不動。關鍵觀察是：任何一條路徑一定有一個「最高點」——路徑上深度最淺的那個節點，路徑在這裡「轉彎」。所以我們可以枚舉「最高點」而不是端點。對每個節點 node，以它為最高點的最佳路徑 = node.val +（左子樹往下延伸的最大貢獻，若為負就丟掉）+（右子樹往下延伸的最大貢獻，若為負就丟掉）。我們設計一個遞迴函式 gain(node)，回傳「從 node 出發、只往下走一條直線」的最大和：gain(node) = node.val + max(0, gain(left), gain(right) 取較大那一邊)。之所以只能選一邊，是因為這個回傳值要交給父節點繼續往上接，路徑不能有分岔。而在計算 gain(node) 的同時，我們用左右兩邊都納入來更新一個全域最大值 best。用 max(0, ...) 是因為：若某子樹的貢獻是負的，最好乾脆不要它，貢獻當作 0。整棵樹只走一遍，時間 O(n)。

The brute force enumerates every pair of nodes as the two endpoints of a path, sums the unique path between them, and takes the max — that is up to O(n^3) and hopeless for n = 3*10^4. The insight: every path has a single highest node — the shallowest node on it, where the path "bends." So instead of enumerating endpoints, enumerate the highest node. For a node acting as the bend, the best path through it is node.val plus the best downward contribution from the left (dropped if negative) plus the best downward contribution from the right (dropped if negative). We write a recursive helper gain(node) returning the maximum sum of a straight downward path starting at node: gain(node) = node.val + max(0, larger of gain(left)/gain(right)). We may keep only one side because this return value gets attached to the parent going upward, and a path cannot fork. While computing gain(node), we combine both sides to update a shared best answer. The max(0, ...) clamp says: if a subtree's contribution is negative, skip it (treat as 0) — that's why the answer for [-10,9,20,...] correctly ignores the negative root. One traversal, O(n) time.

逐步走查 / Walkthrough

Example: root = [-10,9,20,null,null,15,7]. We start best = -∞ (the smallest possible), then DFS visits leaves first (post-order). 我們用 L、R 表示左右子的向下貢獻（已 clamp 過），through = node.val + L + R 是「以此節點為最高點」的候選答案。

Final answer / 最終答案 = best = 42. 注意第 4 步把左右兩邊都納入得到 42，但回傳給父節點時只能選一邊（35），這正是 through 與 gain 的差別。

Solution — C

// 演算法：後序 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;
}

Solution — C++

// 演算法：與 C 版相同。後序 DFS，gain 回傳向下單邊最大和，
// 過程中用 val + 左 + 右 更新成員變數 best；負貢獻 clamp 成 0。
// Algorithm: identical to the C version. Post-order DFS; gain returns the best single-side
// downward sum, while member variable best is updated with val + left + right; negatives clamped to 0.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    // 用成員變數保存目前看過的最大路徑和，取代 C 版的指標傳遞
    // A member variable holds the running best, replacing the C version's pointer passing
    int best = INT_MIN;   // INT_MIN 來自 <climits>，是最小的 int / INT_MIN (from <climits>) is the smallest int

    // 回傳「從 node 只往下走一條直線」的最大貢獻
    // Returns the best contribution going straight down from node
    int gain(TreeNode* node) {
        if (!node) return 0;   // 空指標視為 0 貢獻 / a null pointer contributes 0

        // std::max(0, x) 把負貢獻夾成 0；<algorithm> 提供 std::max
        // std::max(0, x) clamps negative gains to 0; std::max comes from <algorithm>
        int left  = std::max(0, gain(node->left));    // 遞迴左子樹 / recurse left
        int right = std::max(0, gain(node->right));   // 遞迴右子樹 / recurse right

        // 以 node 為轉彎點、同時納入左右的完整路徑候選
        // Candidate path bending at node, using both sides
        best = std::max(best, node->val + left + right);

        // 交給父節點時只能保留較大的一邊 / hand only the larger side up to the parent
        return node->val + std::max(left, right);
    }

public:
    int maxPathSum(TreeNode* root) {
        gain(root);     // 一趟 DFS 就把 best 算好 / a single DFS fills in best
        return best;    // 回傳最終答案 / return the final answer
    }
};

複雜度 / Complexity

• Time: O(n) — n 是節點總數。每個節點只被 gain 呼叫並處理一次（後序遍歷），每次做的都是常數時間的加法與比較。Each node is visited exactly once by gain, doing constant work (a few adds and comparisons); that dominates.
• Space: O(h) — h 是樹的高度，來自遞迴呼叫堆疊的深度。最壞情況（退化成一條鏈）h = n，平衡樹則約 O(log n)。The recursion call stack goes as deep as the tree's height h; worst case (a chain) h = n, balanced tree O(log n).

Pitfalls & Edge Cases

• 負值節點 / negative nodes：答案可能整個是負的（例如樹只有一個節點 -3，答案就是 -3）。所以 best 必須初始化成 INT_MIN，不能設成 0，否則會誤回傳 0。The answer can be negative, so seed best with INT_MIN, never 0.
• clamp 與回傳值的差異 / clamp vs. return value：gain 回傳時只能選一邊（max(left,right)），但更新 best 時可用兩邊（left+right）。搞混這兩者是最常見的錯誤。The upward return keeps one side; the best update uses both. Confusing them is the classic bug.
• 忘記把負貢獻歸零 / forgetting the 0-clamp：若不做 max(0, child)，一個很負的子樹會硬被算進來，壓低答案。max(0, ...) 讓我們可以「選擇不走那條爛路」。Without max(0, child), a very negative subtree drags the total down; the clamp lets us skip a bad branch.
• 空指標 / null pointer：遞迴一定要先檢查 node == NULL / !node 再存取 node->val，否則會當機。題目保證至少 1 個節點，所以 root 不會是 null，但子節點會。Always guard against null before dereferencing; children can be null even though root isn't.
• 整數溢位 / overflow：最大約 3*10^4 個節點、每個最多 1000，總和上限約 3*10^7，遠在 32-bit int 範圍內，不會溢位。The maximum sum (~3*10^7) fits comfortably in a 32-bit int, so no overflow handling is needed.