C++ 32ms and C# 184ms explained solution using a dfs approach


  • 0
    O

    C++ version

    int maxPathSum(TreeNode* root) {
            // check bad input
            if(root == NULL)
                return 0;
            // Initialize max to the minimum value
            int maxSum = numeric_limits<int>::min();
            // Use a helper method and pass the maxSum as reference
            maxPathSumHelper(root, maxSum);
            return maxSum;
        }
        
        int maxPathSumHelper(TreeNode* root, int& maxSum){
            // if the child is null return 0 so there is no any impact in the addition
            if(root == NULL)
                return 0; 
            int leftSum = maxPathSumHelper(root->left, maxSum);
            int rightSum = maxPathSumHelper(root->right, maxSum);
            int closedPathSum = root->val;
            bool onePositiveChild = false;
            // We add a child only if it's value is positive
            if(leftSum > 0){
                closedPathSum += leftSum;
                onePositiveChild = true;
            }
            if(rightSum > 0){
                closedPathSum += rightSum;
                onePositiveChild = true;
            }
            // Compare to the max value
            if(closedPathSum >  maxSum)
                maxSum = closedPathSum;
            // We will return here the maximum sum of opened path:
            // root+left or root+right or root
            int openedPathSum = root->val;
            if(onePositiveChild)
                openedPathSum += (leftSum > rightSum? leftSum : rightSum); 
            return openedPathSum;
        }
    

    C# version

    public int MaxPathSum(TreeNode root) {
        // check bad input
        if(root == null)
            return 0;
        // Initialize max to the minimum value
        int maxSum = int.MinValue;
        // Use a helper method and pass the maxSum as reference
        MaxPathSumHelper(root, ref maxSum);
        return maxSum;
    }
    
    public int MaxPathSumHelper(TreeNode root, ref int maxSum){
        // if the child is null return 0 so there is no any impact in the addition
        if(root == null)
            return 0; 
        int leftSum = MaxPathSumHelper(root.left, ref maxSum);
        int rightSum = MaxPathSumHelper(root.right, ref maxSum);
        int closedPathSum = root.val;
        bool onePositiveChild = false;
        // We add a child only if it's value is positive
        if(leftSum > 0){
            closedPathSum += leftSum;
            onePositiveChild = true;
        }
        if(rightSum > 0){
            closedPathSum += rightSum;
            onePositiveChild = true;
        }
        // Compare to the max value
        if(closedPathSum >  maxSum)
            maxSum = closedPathSum;
        // We will return here the maximum sum of opened path:
        // root+left or root+right or root
        int openedPathSum = root.val;
        if(onePositiveChild)
            openedPathSum += (leftSum > rightSum? leftSum : rightSum); 
        return openedPathSum;
    }

Log in to reply
 

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