后序遍历
二叉树的最大路径和
http://www.nowcoder.com/questionTerminal/da785ea0f64b442488c125b441a4ba4a
求一棵二叉树的最大路径和，可以从二叉树的任意节点出发然后到二叉树的任意节点结束，其实本质就是求以二叉树的某个节点为根节点出发，求其本身与其左右子树构成的最大路径和，这种可能有：
1、其本身构成了最大值
2、其本身与其左右子树构成了最大值
3、其本身与其左子树或者右子树构成了最大值
所以我们采用后序遍历求解。
所以整体的任务就是将二叉树中每个节点为根节点时的最大路径和进行比较，求出其中的最大值即可。
需要注意的是：
在这里，findPathSum函数的返回值定义为以自己为根的一条从根到子结点的最长路径，这个返回值是为了提供给它的父结点计算自身的最长路径用，这个最长路径就是它的左子树返回值（如果大于0的话），加上右子树的返回值（如果大于0的话），再加上自己的值。它是众多可能情况的一种，会有成员变量进行比较，如果大于成员变量res的值，则进行更新。
private int res = Integer.MIN_VALUE;
public int maxPathSum (TreeNode root) {
// write code here
if (root == null){
return 0;
}
if (root.left == null && root.right == null){
return root.val;
}
findPathSum(root);
return res;
}
private int findPathSum(TreeNode root){
if (root == null){
return 0;
}
int sum = root.val;
int leftSum = findPathSum(root.left);
int rightSum = findPathSum(root.right);
if (leftSum > 0)
sum += leftSum;
if (rightSum > 0){
sum += rightSum;
}
res = Math.max(res,sum);
return Math.max(root.val,Math.max(rightSum,leftSum)+root.val);
}
文远知行公司福利 588人发布
查看8道真题和解析