BinaryTreeMaximumPathSum.java

private int max = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root) {
	maxPathSumHelper(root);
	return this.max;
}

public int maxPathSumHelper(TreeNode root) {
	if (root == null) {
		return 0;
	}

	int left = maxPathSumHelper(root.left);
	int right = maxPathSumHelper(root.right);

	// the max on a single path
	int singlePath = Math.max(root.val, Math.max(left, right) + root.val);
	// max across the current node on two sides
	int acrossPath = Math.max(singlePath, left + right + root.val);
	if (acrossPath > this.max) {
		this.max = acrossPath;
	}

	// Note: always want to return the single path for recursion, because you cannot include both path, else,
	// it will not be a path
	return singlePath;
}