NC6题解 | #二叉树中的最大路径和#

递归算法

题目要求所有节点各自的最大路径和

构造一个递归函数，获取每个节点的最大收益=》可以理解为节点的一个衍生属性(类似于深度depth的题目):return Math.max(depth(root.left), depth(root.right)) + 1; 那么每个节点的最大路径和：

Math.max(root.val, root.val + 左子节点收益 + 右子节点收益) 代码用下面的方式，提前去排除负数，省去后面的判断

int maxLeft = Math.max(maxGain(root.left),0);
int maxRight = Math.max(maxGain(root.right),0);
max = Math.max(max, root.val+maxLeft+maxRight);

然后更新全局最大值就是了

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int max = Integer.MIN_VALUE;
    public int maxPathSum (TreeNode root) {
        // write code here
        maxGain(root);
        return max;
    }
    //root节点的收益，必须经过root点，也就是root本身的值必须计算进去
    public int maxGain(TreeNode root){
        if(root == null){
            return 0;
        }
        //左子节点的最大收益或者是0(省去后面判断负数)
        int maxLeft = Math.max(maxGain(root.left),0);
        //右子节点的最大收益或者是0(省去后面判断负数)
        int maxRight = Math.max(maxGain(root.right),0);
        //计算经过root节点的最大路径，更新全局最大值
        max = Math.max(max, root.val+maxLeft+maxRight);
        return root.val + Math.max(maxLeft,maxRight);
    }
}