BinaryTreeMaximumPathSum124.java

/**
 * 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.
 */


public class BinaryTreeMaximumPathSum124 {

 private int maxSum;

 public int maxPathSum(TreeNode root) {
 maxSum = Integer.MIN_VALUE;
 maxBranch(root);
 return maxSum;
 }

 private int maxBranch(TreeNode root) {
 if (root == null) return 0;

 int valueLeft = Math.max(0, maxBranch(root.left));
 int valueRight = Math.max(0, maxBranch(root.right));
 maxSum = Math.max(maxSum, root.val + valueLeft + valueRight);

 return Math.max(valueLeft, valueRight) + root.val;
 }


 public static void main(String[] args) {
 BinaryTreeMaximumPathSum124 btmps = new BinaryTreeMaximumPathSum124();

 TreeNode root1 = new TreeNode(2);
 root1.left = new TreeNode(1);
 root1.right = new TreeNode(3);

 TreeNode root2 = new TreeNode(-3);

 System.out.println(btmps.maxPathSum(root1));
 System.out.println(btmps.maxPathSum(root2));

 }

}