计算节点值之和最大的路径的节点值之和
二叉树的最大路径和
http://www.nowcoder.com/questionTerminal/da785ea0f64b442488c125b441a4ba4a
题目描述
给定一个二叉树，请计算节点值之和最大的路径的节点值之和是多少。
这个路径的开始节点和结束节点可以是二叉树中的任意节点
例如：
给出以下的二叉树，
返回的结果为6
这个路径的开始节点和结束节点可以是二叉树中的任意节点
例如：
给出以下的二叉树，
返回的结果为6
一个节点的最大值 可以是自己 root + left root + right root+left + right;
如果子节点为负数节点 让他的计算值为0 则一个节点的最大值为 root+left + right
爷爷节点 与孙子节点连接的最大值 为 gp + p +left 或者 gp +p + right
//设置一个全局变量用来存储 节点之和的最大值
int max = Integer.MINVALUE;
public int maxPathSum(TreeNode root) {
// 当根节点为null时返回0
if (root == null) {
return 0;
}
help(root);
return max;
}
// 当根节点为null时返回0
if (root == null) {
return 0;
}
help(root);
return max;
}
public int help(TreeNode root) {
if(root == null) {
return 0;
}
if(root == null) {
return 0;
}
//如果子节点为负数节点 让他的计算值为0 则一个节点的最大值为 root+left + right
int left = Math.max(help(root.left), 0);
int right = Math.max(help(root.right), 0);
max = Math.max(max, root.val + left + right);
return Math.max(root.val + left, root.val + right);
}
int left = Math.max(help(root.left), 0);
int right = Math.max(help(root.right), 0);
max = Math.max(max, root.val + left + right);
return Math.max(root.val + left, root.val + right);
}
查看7道真题和解析
投递网易等公司10个岗位 >