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.

Have you met this question in a real interview? Yes Example Given the below binary tree:

  1
 / \
2   3

return 6.

Solution: Divide conquer. The max path have two situations:

1. root to leaf;
2. arbitrary left -> root -> arbitrary right

The getMax will return the first condition since the second is arbitrary situation.

public int maxPathSum(TreeNode root) {
    if(root == null) {
        return 0;
    }
    int[] res = new int[1];
    res[0] = Integer.MIN_VALUE;
    getMax(root, res);
    return res[0];
}

public int getMax(TreeNode root, int[] res) {
    if(root == null) {
        return 0;
    }
    int left = getMax(root.left, res); 
    int right = getMax(root.right, res);
    int tmp = Math.max(root.val + left, Math.max(root.val + right, root.val));
    res[0] = Math.max(res[0], Math.max(tmp, root.val + left + right));
    return tmp;
}