難度困難314
給定一個非空二叉樹，返回其最大路徑和。
本題中，路徑被定義為一條從樹中任意節點出發，達到任意節點的序列。該路徑至少包含一個節點，且不一定經過根節點。
示例 1:
輸入: [1,2,3]1/ \2 3輸出: 6
示例?2:
輸入: [-10,9,20,null,null,15,7]-10/ \9 ?20/ ?\15 ? 7輸出: 42
思路：
解釋鏈接
我簡化代碼，全局答案最大值有一個變量記錄，遞歸函數返回一條路最大和即可
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode(int x) { val = x; }* }*/
class Solution {int max_sum = Integer.MIN_VALUE;public int max_gain(TreeNode node) {if (node == null) return 0;int left = Math.max(max_gain(node.left), 0);int right = Math.max(max_gain(node.right), 0);max_sum = Math.max(max_sum, node.val + left + right);return node.val + Math.max(left, right);}public int maxPathSum(TreeNode root) {max_gain(root);return max_sum;}
}?
)
)
)
)
)
