Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3
return 6

一刷
题解：
题目的意思是, maxPath: 从树中任意到任意点的最大路径，这条路径至少包含一个点。
方法：求出某个branch的sum, 并且在过程中不断利用 maxValue = Math.max(maxValue, left+right+root.val);来更新sum

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int maxValue;
    
    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPathDown(root);
        return maxValue;
    }
    
    private int maxPathDown(TreeNode root){
        if(root==null) return 0;
        int left = Math.max(0, maxPathDown(root.left));
        int right = Math.max(0, maxPathDown(root.right));
        maxValue = Math.max(maxValue, left+right+root.val);
        return Math.max(left, right) + root.val;
    }
}

二刷
思路同上，注意，如果要pop到上一层，只能选一个branch

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int maxVal = Integer.MIN_VALUE;
    
    
    public int maxPathSum(TreeNode root) {
        if(root == null) return 0;
        pathSum(root);
        return maxVal;
    }
    
     public int pathSum(TreeNode root) {
         if(root == null) return 0;
        int left = Math.max(0, pathSum(root.left));
        int right = Math.max(0, pathSum(root.right));
        maxVal = Math.max(maxVal, right+left+root.val);
         return Math.max(left, right) + root.val;
     }
}

三刷
由于是求任意点到任意点的最大值，于是需要在DFS中更新maxVal

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int maxVal = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root == null) return 0;
        pathSum(root);
        return maxVal;
    }
    
    public int pathSum(TreeNode root){
        if(root == null) return 0;
        int left = Math.max(0, pathSum(root.left));//0 discard the branch
        int right = Math.max(0, pathSum(root.right));
        maxVal = Math.max(maxVal, left+right+root.val);
        return Math.max(left, right) + root.val;
    }
}