Binary Tree Maximum Path Sum


  • 0
    K

    where does my solution go wrong?
    I think the maximum path sum is max of three source:
    left tree maximum path sum
    right tree maximum path sum
    the maximum path that passes root
    '''

    public int maxPathSum(TreeNode root) {
    // write your code here
    if (root == null) return Integer.MIN_VALUE;
    int leftPathSum = maxPathSum(root.left);
    int rightPathSum = maxPathSum(root.right);
    int maxSumPassRoot = root.val + helper(maxPathSumFromRoot(root.left), maxPathSumFromRoot(root.right));

        return Math.max(Math.max(leftPathSum, rightPathSum), maxSumPassRoot);
    }
    
    private int maxPathSumFromRoot(TreeNode node) {
        if (node == null) return Integer.MIN_VALUE;
        int leftSum = maxPathSumFromRoot(node.left);
        int rightSum = maxPathSumFromRoot(node.right);
        
        if (leftSum < 0 && rightSum < 0) return node.val;
        return node.val + leftSum >= rightSum ? leftSum : rightSum;
        
    }
    
    private int helper(int a, int b) {
        int ret = 0 + (a >= 0 ? a : 0) + (b >= 0 ? b : 0);
        return ret;
    }
    

    '''


  • 0
    L

    @kevincoding The value of the node maybe negative. So the maximum path sum can be just the root.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.