124. 二叉树中的最大路径和(困难)

主要还是思路问题，对于一个节点，计算以当前节点为顶点的最大路径和。

int max_sum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        scan(root);
        return max_sum;
    }

    public int scan(TreeNode root){
        if(root == null) return 0;
        //计算以左子节点为顶点的最大路径和，如果为负，则舍弃
        int left = Math.max(scan(root.left),0);
        //计算以右子节点为顶点的最大路径和，如果为负，则舍弃
        int right = Math.max(scan(root.right),0);
        //计算以当前节点为顶点的最大路径和，为左字节点最大路径和的值+右子节点最大路径和的值+当前节点值
        max_sum = Math.max(left + right + root.val, max_sum);
        //向父节点返回的，只有当前节点+左子节点，或者当前节点+右子节点的情况
        return Math.max(left,right)+root.val; 
    }