C++ Using BFS as a faster solution, easy to understand


  • 2
    C

    class Codec {
    public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root)
            return "";
        
        queue<TreeNode*> q;
        q.push(root);
        
        string s;
        while(!q.empty())
        {
            auto p = q.front();
            q.pop();
            
            if(!s.empty())
                s+=',';
            
            s+= p ? to_string(p->val) : "#";
            if(p)
            {
                q.push(p->left);
                q.push(p->right);
            }
        }
        
        return s;
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty())
            return nullptr;
        
        int i = 0;       
        auto hasNextNode = [&]()->bool
        {
            return i!=string::npos;
        };
        
        auto getNextNode = [&]()->TreeNode*
        {
            TreeNode* p = nullptr;
            int j =data.find_first_of(',', i);
            string str = data.substr(i, j!=string::npos ? j-i : string::npos);
            if(str=="#")
                p = nullptr;
            else
            {
                p = new TreeNode(stoi(str));
            }
            
            i = (j==string::npos)?string::npos : j+1;
            
            return p;
        };
        
        queue<TreeNode*> q;
        TreeNode* root = getNextNode();
        q.push(root);
        while(!q.empty())
        {
            int n = q.size();
            for(int i = 0;i<n;i++)
            {
                auto p = q.front();
                q.pop();
                
                if(!p)
                    continue;
                
                p->left = hasNextNode() ? getNextNode() : nullptr;
                p->right = hasNextNode() ? getNextNode() : nullptr;
                
                q.push(p->left);
                q.push(p->right);
            }
        }
        
        return root;
    }
    

    };


  • 1
    F

    brilliant!!really logical and easy to follow


Log in to reply
 

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