Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum

23%

Accepted

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.

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
     int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        // write your code here
        _getMaxSum(root);
        return maxSum;
    }
   
    private int _getMaxSum(TreeNode root){
        if(root == null) return 0;
        int left = _getMaxSum(root.left);
        int right = _getMaxSum(root.right);
        int sum = left > 0 ? left : 0;
        sum += right > 0 ? right : 0;
        sum += root.val;
        maxSum = Math.max(maxSum, sum);
        return Math.max(left, right) + root.val;
    }
}