Simple recursive yet still accepted as best in cpp


  • 0
    class Solution {
    private:
        int traverse(TreeNode* root, int& maxSum)
        {
            if(!root) return 0;
            int lMax = max(0, traverse(root->left, maxSum));
            int rMax = max(0, traverse(root->right, maxSum));
            maxSum = max(maxSum, lMax+rMax+root->val);
            return max(lMax, rMax)+root->val;
        }
    public:
        int maxPathSum(TreeNode* root) {
            int maxSum = INT_MIN;
            traverse(root, maxSum);
            return maxSum;
        }
    };

  • 0

    What's the usage of return max(lMax, rMax)+root->val; in maxPathSum().

    I can't see it's usage in maxPathSum(). I tried return maxSum in traverse(), I just failed. Can you explain why please?


  • 1

    @zhugejunwei We're tying to affect two variables here.

    • first we are to select the maxSum starting from any possible node in the tree
    • second the maximal sum of just one side started from the node - just one side, left or right so that we can actually maximise the maxSum globally - one side of it can be negative and at that time we should overlook it.

Log in to reply
 

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