124. 二叉树中的最大路径和

这题使用递归解决

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } public int maxGain(TreeNode node){ if(node == null){ return 0; } //递归找左右子节点最大贡献值,贡献值如果是负数就设为零 int leftGain = Math.max(maxGain(node.left),0); int rightGain = Math.max(maxGain(node.right),0); //该节点的贡献值就是该节点的值加左右子节点最大贡献值 int priceNewpath = node.val + leftGain+ rightGain; maxSum = Math.max(priceNewpath,maxSum); return node.val + Math.max(leftGain,rightGain); } }