二叉树中的最大路径和 （有点生疏了）

timudaima

class Solution {
    int maxSum = Integer.MIN_VALUE;             // 初始化也有坑。 本题最大路径和有可能是负数，所以maxsum初始不能为0
    public int maxPathSum(TreeNode root) {

        if(root == null){
            return 0;
        }

        dfs(root);//返回值没有用，因为dfs（root）的含义，不是求最大路径，只是求以root为根的最大的半边路径
        return maxSum;


    }

    public int dfs(TreeNode root){
       if(root == null){    // 递归出口
           return 0;
       }

      
        
        int leftsum = Math.max(0, dfs(root.left));
        int rightsum = Math.max(0, dfs(root.right));



        // 真正的求最大值得程序在这maxSum最大值有可能在过程中取得

       maxSum = Math.max(maxSum, leftsum + rightsum + root.val);  // 第543题，只是求任两点之间最长路径，所以根节点只是一个点，对结果没有贡献，
                                                                  // 但是本题，试求路径上结点值的和，根节点也有贡献，所以此处要加上 root.val

       return Math.max(leftsum,rightsum) + root.val ;              //返回值是亮点，是返回以root为根的一半子树的最大路径和     同理， 根节点有贡献



    }


}