Post order traversal recursive C++ implementation


  • 0
    V

    Time complexity - O(n) - 32ms OJ

    class Solution {
    public:
        int maxPathSum(TreeNode* root) {
            int maxSum=-65535;
            maxPathSumUtil(root, maxSum);
            return(maxSum);
        }
        
        int maxPathSumUtil(TreeNode *root, int &maxSum) {
            if(root == NULL) {
                return (-65535);
            }
            int currMaxSum=0;
            int currThreeMaxSum=0;
            int leftSum = maxPathSumUtil(root->left, maxSum);
            int rightSum = maxPathSumUtil(root->right, maxSum);
            int allSum = leftSum + rightSum + root->val;
            leftSum += root->val;
            rightSum += root->val;
            currThreeMaxSum = max(leftSum, rightSum);
            currThreeMaxSum = max(currThreeMaxSum, root->val);
            currMaxSum = max(currThreeMaxSum, allSum);
            if(currMaxSum > maxSum) {
                maxSum = currMaxSum;
            }
            return(currThreeMaxSum);
        }
    };
    

Log in to reply
 

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