Binary Tree Maximum Path Sum @LeetCode

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.

	package leetcode.tree;
	/**
	* Thought: check every subtree to findout the maxPath, then go upstair.
	*
	* singlePath = Math.max(left.singlePath, right.singlePath) + root.val --> find out the MaxPath of last two layer TreeNode.
	* maxPath = Math.max(left.maxPath, right.maxPath) --> find out the maxPath of left and right subtree
	*
	* maxPath = Math.max(maxPath, left.singlePath + right.singlePath + root.val); negative condition already in.
	* --> if subtree is larger than leftsinglePath + rightsinglePath, will not cross root, like follows
	* 4 + 2 + 5 > 7 + 1 + 3 --> maxPath will be 4 --> 2 --> 5, if 3 replaces 5, maxPath will be 4 --> 2 --> 1 --> 3
	*
	* 1
	* 2 3
	* 4 5
	*
	* Take care: there may be negative weight TreeNode, there's will be more conditions.
	* Condition: singlePath = Math.max(singlePath, 0); --> if single path sum less than 0, abort
	*
	*
	*
	* @author jeffwan
	* @date Feb 12, 2014
	*/
	public class MaxPathSum {
	public int maxPathSum(TreeNode root) {
	ResultType result = helper(root);
	return result.maxPath;
	}
	private ResultType helper(TreeNode root) {
	if(root == null) {
	return new ResultType(0, Integer.MIN_VALUE);
	}
	// divide
	ResultType left = helper(root.left);
	ResultType right = helper(root.right);
	// conquer
	int singlePath = Math.max(left.singlePath, right.singlePath) + root.val;
	singlePath = Math.max(singlePath, 0);
	int maxPath = Math.max(left.maxPath, right.maxPath);
	maxPath = Math.max(maxPath, left.singlePath + right.singlePath + root.val);
	return new ResultType(singlePath, maxPath);
	}
	private class ResultType {
	int singlePath;
	int maxPath;
	ResultType(int singlePath, int maxPath) {
	this.singlePath = singlePath;
	this.maxPath = maxPath;
	}
	}
	// TreeNode
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode (int x) {
	val = x;
	}
	}
	}

view raw MaxPathSum.java hosted with ❤ by GitHub