题解 | #二叉树中的最大路径和# 注意符号位丢失

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public int maxVal = Integer.MIN_VALUE;
    public int subPathSum(TreeNode root) {
        if (root == null) return -1001;
        if(root.left == null && root.right == null){
            maxVal = root.val;
            return root.val;
        }
        
        // write code here
        // 状态转化公式
        int leftMaxPathSum = subPathSum(root.left);
       // System.out.println(leftMaxPathSum);
        maxVal = Math.max(maxVal, leftMaxPathSum);

        int rightMaxPathSum = subPathSum(root.right);
       // System.out.println(rightMaxPathSum);
        maxVal = Math.max(maxVal, rightMaxPathSum);

       maxVal = Math.max(maxVal, leftMaxPathSum + rightMaxPathSum + root.val);
        int subSum = leftMaxPathSum > rightMaxPathSum ? leftMaxPathSum :
                     rightMaxPathSum;

        if (subSum > 0) {
             
            maxVal = Math.max(maxVal, root.val + subSum);
            return root.val + subSum;
        } else {
           maxVal = Math.max(maxVal, root.val);
            return root.val;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxPathSum (TreeNode root) {
        subPathSum(root);
        return maxVal;
    }
}

if (root == null) return -1001; 如果设置为 Integer.MIN_VALUE; 两者求和，会使得符号位丢失。