versin at: 2022-04-20

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

/**
1. 首先一个path 一定是从叶子节点开始到另一个叶子节点, 或者是上述path的sub-path
2. 那么对于任意一棵树的根节点, 我们可以算出它到叶子节点的path的最大和, 与由它作为中继的路径和
3. 当前路径的最大和 = MAX(left + val, right + val, val)
4. 最为中继节点的最大和 = MAX(当前路径的最大和, val + left  + right)
5. 统计所有根作为中继节点的路径和的最大值就是所求
*/

class Solution {
    public int maxPathSum(TreeNode root) {
        int[] result = new int[]{Integer.MIN_VALUE};

        maxPathSum(root, result);

        return result[0];
    }

    public int maxPathSum(TreeNode root, int[] result) {
        if (root == null) return 0;

        int left = maxPathSum(root.left, result);
        int right = maxPathSum(root.right, result);
        int maxSubPathSum = Math.max(left, right);
        int curMaxPathSum = Math.max(0, maxSubPathSum) + root.val;

        int[] candidates = {curMaxPathSum, root.val + left + right, result[0]};
        result[0] = Math.max(result[0], Math.max(curMaxPathSum, root.val + left + right));

        return curMaxPathSum;
    }
}

/**
0. 最大路径和 -》 求每个路径和取最大值 -》 经过一个点的路径和等于左边的最长路径+右边的最长路径, val可能为负, 所以向左右扩展都是可选的
1. 一个点能参与的路径的最大和: MAX (self, self + left , self + right, self+left + right) 
                                ( 不扩展, 向左扩展,    向右扩展,      左右都扩展)
2. 一个点开始到达其叶子节点之间的最大长度 MAX(self, self + left , self + right)
                                            (不扩展, 从左边走,   从右边走)

3. dfs 一个点到达叶子的最大路径和
3.1 搜素顺序: 分别获取左右儿子的结果, 并且返回 2中判断的结果, 同时更新1的全局结果
3.2 搜索状态: cur | res
3.3 剪枝: ~ 

4. testCase:  树的结构：null，只包含一边的子树，一边子树的左右子树都很深，另一半只有一个节点
             val 的值： 正数，负数，0 ，随机数
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxPathSum(TreeNode root) {
        TreeNode res = new TreeNode(Integer.MIN_VALUE);
        dfs(root, res);
        return res.val;
    }

    public int dfs(TreeNode cur, TreeNode res){
        if (cur == null) return 0;
        int left = dfs(cur.left, res);
        int right = dfs(cur.right, res);
        int depth = Math.max(cur.val, cur.val + Math.max(left, right));
        res.val = Math.max(res.val, Math.max(depth, cur.val + left + right));
        return depth;
    }
}