Straightforward BSF solution


  • 0
    C

    BSF in (deserialize), BSF out (serialize)

    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
    
            list<TreeNode*> queue;
            queue.push_back(root);
    
            stringstream result;
    
            if(root)
            {
                while(not queue.empty())
                {
                    auto curr_node = queue.front();
                    queue.pop_front();
    
                    if(curr_node)
                    {
                        if(curr_node != root)
                            result << ',';
                        result << curr_node->val;
                        queue.push_back(curr_node->left);
                        queue.push_back(curr_node->right);
                    }
                    else
                        result << ",n";
                }
            }
            return result.str();
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
    
            stringstream sstr(data);
            string token;
            TreeNode* root = nullptr;
            int val;
    
            list<TreeNode*> queue;
            const string NULLTOK = "n";
    
            if(getline(sstr, token, ','))
            {
                if(token != NULLTOK)
                {
                    stringstream valstream(token);
                    valstream >> val;
                    root = new TreeNode(val);
                }
            }
            else
            {
                return root;
            }
    
            queue.push_back(root);
    
            while(not queue.empty())
            {
                auto curr_node = queue.front();
                queue.pop_front();
    
                string tokenl(NULLTOK), tokenr(NULLTOK);
                TreeNode* tnoder = nullptr;
                TreeNode* tnodel = nullptr;
    
                if(getline(sstr, tokenl, ',') and tokenl != NULLTOK)
                {
                    stringstream valstream(tokenl);
                    valstream >> val;
                    tnodel = new TreeNode(val);
                }
                if(getline(sstr, tokenr, ',') and tokenr != NULLTOK)
                {
                    stringstream valstream(tokenr);
                    valstream >> val;
                    tnoder = new TreeNode(val);
                }
                if(curr_node)
                {
                    curr_node->left = tnodel;
                    curr_node->right = tnoder;
                    if(tnodel)
                        queue.push_back(tnodel);
                    if(tnoder)
                        queue.push_back(tnoder);
                }
            }
    
            return root;
        }
    };
    

  • 0
    C

    That's C++ language.


Log in to reply
 

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