題目
#

leetcode 124 - Binary Tree Maximum Path Sum (題目說明請點連結)

題目簡述
#

給定一個二元樹，找到其中的最大路徑和。路徑可以從任意節點開始，到任意節點結束，但必須是從父節點到子節點的連續路徑。

範例
#

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: 最佳路徑為 2 -> 1 -> 3，路徑和為 2 + 1 + 3 = 6。

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: 最佳路徑為 15 -> 20 -> 7，路徑和為 15 + 20 + 7 = 42。

解題思路
#

題目要求找到二叉樹中的最大路徑和。路徑可以從任意節點開始，到任意節點結束，但必須是從父節點到子節點的連續路徑。

解法
#

使用 深度優先搜索（DFS） 來解決：

對於每個節點，計算左子樹和右子樹的最大路徑和。
如果子樹的路徑和為負數，則不選擇該子樹（設為0）。
更新全局最大值：左子樹路徑和 + 右子樹路徑和 + 當前節點值。
返回以當前節點為根的最大路徑和（只能選擇左子樹或右子樹之一）。

詳細步驟說明
#

步驟 1：遍歷節點 15

dfs(15) 調用 dfs(null) 和 dfs(null)，都返回 0
left = max(0, 0) = 0, right = max(0, 0) = 0
更新 max = max(0 + 0 + 15, max) = 15
返回 max(0 + 15, 0 + 15) = 15

步驟 2：遍歷節點 7

dfs(7) 調用 dfs(null) 和 dfs(null)，都返回 0
left = max(0, 0) = 0, right = max(0, 0) = 0
更新 max = max(0 + 0 + 7, 15) = 15
返回 max(0 + 7, 0 + 7) = 7

步驟 3：遍歷節點 20

dfs(20) 調用 dfs(15) 和 dfs(7)
left = max(15, 0) = 15, right = max(7, 0) = 7
更新 max = max(15 + 7 + 20, 15) = 42
返回 max(15 + 20, 7 + 20) = 35

步驟 4：遍歷節點 9

dfs(9) 調用 dfs(null) 和 dfs(null)，都返回 0
left = max(0, 0) = 0, right = max(0, 0) = 0
更新 max = max(0 + 0 + 9, 42) = 42
返回 max(0 + 9, 0 + 9) = 9

步驟 5：遍歷根節點 -10

dfs(-10) 調用 dfs(9) 和 dfs(20)
left = max(9, 0) = 9, right = max(35, 0) = 35
更新 max = max(9 + 35 + (-10), 42) = max(34, 42) = 42
返回 max(9 + (-10), 35 + (-10)) = max(-1, 25) = 25

最終結果：42

最佳路徑是 15 → 20 → 7，路徑和為 15 + 20 + 7 = 42。

完整程式碼
#

java

class Solution {
    // 全局變數，記錄最大路徑和
    int max = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        // 調用 DFS 遍歷整棵樹
        dfs(root);
        return max; // 返回全局最大值
    }

    /**
     * DFS 遍歷函數
     * @param root 當前節點
     * @return 返回以當前節點為根的最大路徑和（只能選擇左子樹或右子樹之一）
     */
    public int dfs(TreeNode root) {
        // 邊界條件：空節點返回 0
        if (root == null) {
            return 0;
        }

        // 遞歸計算左子樹的最大路徑和，如果為負數則不選擇（設為0）
        int left = Math.max(dfs(root.left), 0);
        // 遞歸計算右子樹的最大路徑和，如果為負數則不選擇（設為0）
        int right = Math.max(dfs(root.right), 0);
        
        // 更新全局最大值：左子樹路徑和 + 右子樹路徑和 + 當前節點值
        // 這代表經過當前節點的路徑（可以同時選擇左右子樹）
        max = Math.max(left + right + root.val, max);

        // 返回以當前節點為根的最大路徑和
        // 只能選擇左子樹或右子樹之一，加上當前節點值
        return Math.max(left + root.val, right + root.val);
    }
}