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); } }