package code;
/*
 * 124. Binary Tree Maximum Path Sum
 * 
 * Hard
 * Tree, Depth-first Search
 * V
 * TipsV
 *      lc112, lc113, lc437, lc129, lc124, lc337, lc543, lc1026
 */
public class lc124 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    int res = Integer.MIN_VALUE;      //0
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }
    public int dfs(TreeNode root){
        if(root==null)
            return 0;
        int left = Math.max(dfs(root.left),0);
        int right = Math.max(dfs(root.right),0);
        res = Math.max(res, left+right+root.val);   //
        return Math.max(left,right)+root.val;
    }
}