学步园

很有难度的一道题，主要是最大和的可能性很多，不知道如何分情况。

关键点1：

分析：http://fisherlei.blogspot.com/2013/01/leetcode-binary-tree-maximum-path-sum.html

For each node like following, there should be four ways existing for max path:

1. Node only （因为本题中的节点可能是负值！）
2. L-sub + Node
3. R-sub + Node
4. L-sub + Node + R-sub

Keep trace the four path and pick up the max one in the end.  

关键点2：明确递归函数的返回值是什么：这本题中返回值表示通过root节点能走到root的parent的最大和，这个值作为返回对象返给调用父函数

因为在Java中无法像C++一样引用传值或者利用指针传值，以前的解决办法是用全局变量。

今天找到更好的办法，就是利用数组传值！

http://leetcodenotes.wordpress.com/2013/11/04/leetcode-binary-tree-maximum-path-sum-%E6%A0%91%E4%B8%AD%E4%BB%BB%E6%84%8F%E4%B8%A4%E7%82%B9%E9%97%B4%E6%9C%80%E5%A4%A7path-sum/

package Level4;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;

import Utility.TreeNode;

/**
 * Binary Tree Maximum Path Sum
 * 
 *  Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.
 *
 */
public class S124 {

	public static void main(String[] args) {
		TreeNode root = new TreeNode(0);
		System.out.println(maxPathSum(root));
	}
	
	
	public static int maxPathSum(TreeNode root) {
		int[] max = {Integer.MIN_VALUE};		// 因为Java里都是pass by value所以利用数组传！
        rec(root, max);
        return max[0];
    }
	
	public static int rec(TreeNode root, int[] max){
		if(root == null){
        	return 0;
        }
		
        int leftSubtreeMaxSum = rec(root.left, max);		// 左子树的最大和
        int rightSubtreeMaxSum = rec(root.right, max);		// 右子树的最大和
        int arch = leftSubtreeMaxSum + root.val + rightSubtreeMaxSum;		// 从左子树经过root到右子树的最大和
        
        // 表示通过root节点能走到root的parent的最大和，这个值作为返回对象返给调用父函数
        // 只有3中情况: 1 从左子树到root再到parent
        // 2 从右子树到root再到parent
        // 3 直接从root到parent
        // 注意arch那条路是不可能走到parent，因为那条路已经经过root了，除非折回来重复走！但这是不允许的
        int maxPathAcrossRootToParent = Math.max(root.val, Math.max(leftSubtreeMaxSum, rightSubtreeMaxSum)+root.val);
        
        // max[0] 保存在所有递归过程中的最大值，这时也要考虑arch可能最大
        max[0] = Math.max(max[0], Math.max(arch, maxPathAcrossRootToParent));
        
        return maxPathAcrossRootToParent;
	}

}