题解 | #二叉树中的最大路径和#
二叉树中的最大路径和
http://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型
*/
static int maxSum = Integer.MIN_VALUE;;
public int maxPathSum (TreeNode root) {
gainMax(root);
return maxSum;
}
//包括头节点时，经过头节点至叶子节点的累加和的最大值
public static int gainMax(TreeNode root){
if (root == null){
return 0;
}
//左节点所能提供的最大累加和,只有大于0，才会被选择
int leftGainMax = Math.max(0, gainMax(root.left));
//右节点所能提供的最大累加和
int rightGainMax = Math.max(0, gainMax(root.right));
//经过该头节点所能达到的最大值
int rootGainMax = root.val + leftGainMax + rightGainMax;
//更新最大值数据
maxSum = Math.max(maxSum, rootGainMax);
//返回值只包括左右中较大的一部分
return root.val + Math.max(leftGainMax, rightGainMax);
}
}
小天才公司福利 475人发布
，
查看21道真题和解析