Short C++ BFS solution with stringstream (26ms beating 91%)


  • 0
    F

    This solution benefits from stringstream to do stream building and parsing. I was surprised that it is quite fast, I always thought that streams are turtle slow.

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) return "";
        
        ostringstream ss;
        queue<TreeNode*> q;
        q.push(root);
        
        while (!q.empty()) {
            auto curr = q.front();
            q.pop();
            
            if (curr != nullptr) {
                ss << curr->val;
            
                if (curr->left) q.push(curr->left);
                else q.push(nullptr);
                
                if (curr->right) q.push(curr->right);
                else q.push(nullptr);
            }
            
            ss << ",";
        }
        
        return ss.str();
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;
        
        istringstream ss(data);
        TreeNode* root = nullptr;
        string token;
        
        getline(ss, token, ',');
        root = new TreeNode(stoi(token));
    
        queue<TreeNode*> q;        
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            
            getline(ss, token, ',');
            if (!token.empty()) {
                node->left = new TreeNode(stoi(token));
                q.push(node->left);
            }
            
            getline(ss, token, ',');
            if (!token.empty()) {
                node->right = new TreeNode(stoi(token));
                q.push(node->right);
            }
        }
        
        return root;
    }
    

Log in to reply
 

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