LeetCode 124題 求二叉樹中最大路徑和

路徑 被定義為一條從樹中任意節點出發，沿父節點-子節點連接配接，達到任意節點的序列。同一個節點在一條路徑序列中 至多出現一次 。該路徑 至少包含一個 節點，且不一定經過根節點。

路徑和 是路徑中各節點值的總和。

給你一個二叉樹的根節點 root ，傳回其 最大路徑和 。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

示例 1：

輸入：root = [1,2,3]
輸出：6
解釋：最優路徑是 2 -> 1 -> 3 ，路徑和為 2 + 1 + 3 = 6
           

示例 2：

輸入：root = [-10,9,20,null,null,15,7]

輸出：42

解釋：最優路徑是 15 -> 20 -> 7 ，路徑和為 15 + 20 + 7 = 42

class TreeNode {
    int val;
    TreeNode left,right;
    public TreeNode() {}

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

}
           

/**
 *解題思路：
 *1.max左子樹sum
 *2.max右子樹sum
 *3.root跟節點
 *4.max左子樹sum + max右子樹sum + root
 */
class Solution {
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        oneSideSum(root);
        return ans;
    }

    //後序周遊
    int oneSideSum(TreeNode root) {
        //終止條件
        if(root == null) return 0; 
        //若小于0則不相加，賦0
        int leftMax = Math.max(0, oneSideSum(root.left));
        int rightMax = Math.max(0, oneSideSum(root.right));
        //記錄最大值
        ans = Math.max(ans, leftMax + rightMax + root.val);
        return Math.max(leftMax, rightMax) + root.val;
    }
}