C++ recursive solution using pair to track results


  • 0
    B

    the first element in pair is the maximum single pathsum
    the second element in pair is the maximum pathsum for the subtree root at given node

    class Solution {
    public:
        int maxPathSum(TreeNode* root) 
        {
            if(!root) return 0;
            return help(root).second;
        }
        
        pair<int,int> help(TreeNode* root)
        {
            if(!root) return make_pair(INT_MIN,INT_MIN);
            pair<int,int>left = help(root->left), right = help(root->right);
            int first = root->val + max(max(0, left.first), max(0, right.first));
            int second = root->val + max(0, left.first) + max(0, right.first);
            return make_pair(first, max(second, max(left.second, right.second)));
        }
    };

Log in to reply
 

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