1、前言

2、思路

此题的思路是：

• 题目的描述为一棵二叉树，并且是选定任意一个节点开始求出最大路径。我们先不管路径线路是怎样，先将每个节点的路径抽象为：left + right + root，如果 left 或 right 有一个小于0，则将作为0代替，即不要这边的值。那么对某一个 root 来说，我先求它 left 的最大值，再求它 right 的最大值，然后全局最大值与他比较，找出最大的一个。但是返回上层的时候，只能取一边的路径，所以需要找出 max(left, right)，再加上自身的。

3、代码

class Solution {

    private int res = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        oneSideMax(root);
        return res;
    }

    private int oneSideMax(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = Math.max(0, oneSideMax(root.left));
        int right = Math.max(0, oneSideMax(root.right));
        res = Math.max(res, left + right + root.val);
        return Math.max(left, right) + root.val;
    }
}