Why both my recursion and iteration code TLE with input "[1,1,#,1,#...,1,#,1] 1000"


  • 0
    C

    I tested both versions in vs2012 with input "[1,1,#,1,#...,1,#,1] 1000", it outputs correctly, so what's wrong with my code?

    update:

    AC now....I know the solution below is incorrect, but it should get WA, just want to know why it TLE on the above test case ...


    recursion:

    class Solution {
    public:
        bool isLeaf(const TreeNode *nd){
            return nd->left==0 && nd->right==0;
        }
        
        void pushVec(vector<vector<int> > &res, const TreeNode *rt, const int sum, int val, vector<int> &path){
            path.push_back(rt->val);
            int cursum=val+rt->val;
            if(sum==cursum && isLeaf(rt))
                res.push_back(path);
            
            if(rt->left){
                pushVec(res, rt->left, sum, cursum, path);
                path.pop_back();
            } 
            if(rt->right) pushVec(res, rt->right, sum, cursum, path);
        }
        
        vector<vector<int> > pathSum(TreeNode *root, int sum) {
            vector<vector<int> > res;
            vector<int> path;
            if(root!=0)
                pushVec(res, root, sum, 0, path);
            return res;
        }
    };
    

    iteration:

    class Solution {
    public:
        bool isLeaf(const TreeNode *nd){
            return nd->left==0 && nd->right==0;
        }
        
        vector<vector<int> > pathSum(TreeNode *root, int sum) {
            vector<vector<int> > res;
            vector<int> path;
            
            int cursum=0;
            stack<TreeNode*> ndstk;
            stack<int> sumstk;
            while(1){
                while(root!=0){
                    path.push_back(root->val);
                    cursum+=root->val;
                    
                    ndstk.push(root);
                    sumstk.push(cursum);
                    root=root->left;
                }
                if(ndstk.empty())
                    break;
                
                root=ndstk.top();
                ndstk.pop();
                cursum=sumstk.top();
                sumstk.pop();
                if(sum==cursum && isLeaf(root)){
                    res.push_back(path);
                }
                if(root->left)
                    path.pop_back();
                
                root=root->right;
            }
            
            return res;
        }
    };

  • 0
    W

    As for the iterative version I think you should put
    path.pop_back();
    to the last line of pushVec( ) basically after calling pushvec on the right child.

    due to this error, push and pop is not paired for path , thus path keeps growing and in the end it just takes too long to push object on to the path vector. Thus, TLE.


Log in to reply
 

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