Home > Back-end >  leetcode.com/problems/maximum-binary-tree/ is giving stack overflow runtime error for my recursive c
leetcode.com/problems/maximum-binary-tree/ is giving stack overflow runtime error for my recursive c

Time:09-24

gave this error :

AddressSanitizer:DEADLYSIGNAL

==34==ERROR: AddressSanitizer: stack-overflow on address 0x7ffd70bb3ff8 (pc 0x0000002a0876 bp 0x000000000018 sp 0x7ffd70bb3fe0 T0) ==34==ABORTING

My code for it:

class Solution {
public:
        int recur(TreeNode* root,vector<int>& nums){
        auto maxi=max_element (nums.begin(), nums.end());
        vector<int> a;
        int sta=maxi-nums.begin();
        for(int i=sta 1;i<nums.size();i  ){
            a.push_back(nums[i]);
            
        }
        nums.erase(maxi 1,nums.end());//maxi 1 
        
        if(nums.size()>0){
            root->left=new TreeNode(recur(root,nums));
        }
        if(a.size()>0){
            root->right=new TreeNode(recur(root,a));
        }
        return *maxi;
    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
                auto maxi=max_element (nums.begin(), nums.end());
        
        TreeNode* root=new TreeNode(*maxi);
        vector<int> a;
        int sta=maxi-nums.begin();
        for(int i=sta 1;i<nums.size();i  ){
            a.push_back(nums[i]);
            
        }
        nums.erase(maxi 1,nums.end());//maxi 1 
        if(nums.size()>0)
        root->left=new TreeNode(recur(root,nums));
        if(a.size()>0)
        root->right=new TreeNode(recur(root,a));
        
        return root;
    }
};

Could somebody help me out I cant figure out the problem with it.

CodePudding user response:

Could somebody help me out I cant figure out the problem with it.

Your code will perform an endless recurrence until the stack overflows.

This happens because the maximum value remains in nums, even after you chop of all values that follow it. So the next time you call recur, the same maximum value will be found, and the same will happen over and over again.

You should replace the argument maxi 1 to maxi in both your calls of ´.erase`, so that the maximum value you found, is eliminated from the vector.

NB: This algorithm is not the most efficient. Try to build the tree by iterating the vector from left to right in one sweep, keeping track of where the next node should be added to what you already have...

  • Related