Accepted c++ non_recursive solution (using queue)


  • 0
    A

    44ms,it is slower than recursive solution,why?
    I use '#' to represent NULL pointer.

    class Codec {
    public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string result;
        if(!root)
        return result;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty())
        {
            
            int n=q.size();
            for(int i=0;i<n;i++)
            {
                TreeNode *temp=q.front();
                q.pop();
                if(!temp)
                {
                    result+="#,";
                    
                }
                else
                {
                    char ch[20];
                    sprintf(ch,"%d",temp->val);
                    
                    result+=ch;
                    result+=",";
                    q.push(temp->left);
                    q.push(temp->right);
                    
                }
            }
            
        }
        return result.substr(0,result.size()-1);
        
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty())
        return NULL;
        int start=0;
        while(start<data.size()&&data[start]!=',')
        start++;
        string first=data.substr(0,start);
        char *firstp;
        int num=static_cast<int>(strtol(first.c_str(),&firstp,10));
        queue<TreeNode *> q;
        TreeNode *root=new TreeNode(num);
        q.push(root);
        while(!q.empty())
        {
            int n=q.size();
            for(int i=0;i<n;i++)
            {
                
                TreeNode *head=q.front();
                q.pop();
                start++;
                int j=start;
                if(data[j]=='#')                             //left
                start++;
                else
                {
                    while(start<data.size()&&data[start]!=',')
                    start++;
                    string temp=data.substr(j,start-j);
                    char *tempp;
                    int k=static_cast<int>(strtol(temp.c_str(),&tempp,10));
                    TreeNode *l=new TreeNode(k);
                    head->left=l;
                    q.push(l);
                    
                }
                start++;
                j=start;
                if(data[j]=='#')                              //right
                start++;
                else
                {
                    while(start<data.size()&&data[start]!=',')
                    start++;
                    string temp=data.substr(j,start-j);
                    char *tempp;
                    int k=static_cast<int>(strtol(temp.c_str(),&tempp,10));
                    TreeNode *r=new TreeNode(k);
                    head->right=r;
                    q.push(r);
                    
                }
                
                
                
            }
        }
        return root;
    }
    

    };


  • 0
    C

    I am also implementing non-recursive methods. One very general suggestion: you don't need the for-loop inside the iteration. The while loop works perfectly fine. (see sample below). The time complexity is exactly the same, but makes the code shorter.

    while (!q.empty()) {
        TreeNode* head = q.front();
        q.pop();
        // Do actual work here
    }
    

    Besides that, I had some trouble understanding your approach of extracting each substring. It seems that you are doing a lot of substr() and static_cast<int>(strtol()); Ideally you'd do them once for each substring. Can you briefly explain that part?

    My approach is

    TreeNode* getNode(const string& data, size_t& start_pos) {
        if (start_pos >= data.length() - 1) {
            return NULL;
        }
        size_t iterate = start_pos + 1;
        while (iterate < data.length()) {
            if (data.at(iterate) == ',') {
                string str = data.substr(start_pos, (iterate-start_pos));
                start_pos = iterate + 1;
                if (str == "#") {
                    return NULL;
                } else {
                    return new TreeNode(atoi(str.c_str()));
                }
            }
            ++iterate;
        }
    }
    

Log in to reply
 

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