Binary Tree Maximum Path Sum

给定一个二叉树，找到图中具有最大和的路径。路径必须有至少一个node，从任意节点开始，任意节点结束，不需要经过root节点。节点值可以为负数。

算法如下(参考https://discuss.leetcode.com/topic/4407/accepted-short-solution-in-java):

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
	//该算法主要通过对比maxValue变量来记录最大路径长度
    int maxValue;	
    
    public int maxPathSum(TreeNode root) {
        maxValue = Integer.MIN_VALUE;
        maxPathGoingDown(root);
        return maxValue;
    }
    
    public int maxPathGoingDown(TreeNode node) {
        if (node == null) return 0;
        
        //对节点值为负数作出考虑，即当左右子女值均为负数的时候，则路径不向左右节点延伸
        int left = Math.max(0, maxPathGoingDown(node.left));
        int right = Math.max(0, maxPathGoingDown(node.right));
        
        //对当前最大路径和左右子女根到叶节点最大路径（也有可能在中途停止）与当前节点值的和比较
        maxValue = Math.max(maxValue, left + right + node.val);
        
        //返回值是当前节点作为根到叶节点的最大路径（可能中途停止）
        return Math.max(left, right) + node.val;
    }
}