C++ 36ms solution


  • 6
    S

    The serialization format looks like: 1[2[3,],4[5,6[,7]]], O(n) one-pass processing for both ser/deser

    class Codec {
    private:
    	void serialize(TreeNode* root, stringstream& ss) {
    		if (root == nullptr) return;
    
    		ss << root->val;
    		if (root->left != nullptr || root->right != nullptr) {
    			ss << "[";
    			serialize(root->left, ss);
    			ss << ",";
    			serialize(root->right, ss);
    			ss << "]";
    		}
    	}
    
    	TreeNode* deserialize(string& data, int& pos) {
    		int n = data.size();
    		int i = pos;
    		bool foundL = false;
    
    		while (i < n) {
    			if (data[i] == ',' || data[i] == ']') break;
    
    			if (data[i] == '[') {
    				foundL = true;
    				break;
    			}
    
    			i++;
    		}
    
    		if (i == pos && i < n) return nullptr;
    
    		int val = atoi(data.substr(pos, i - pos).c_str());
    		auto node = new TreeNode(val);
    
    		if (i == n) return node;
    
    		pos = i;
    		if (foundL) {
    			// find a '['
    			pos++; // skip '['
    			node->left = deserialize(data, pos);
    			pos++; // skip ','
    			node->right = deserialize(data, pos);
    			pos++; // skip ']'
    		}
    
    		return node;
    	}
    
    public:    
    	// Encodes a tree to a single string.
    	string serialize(TreeNode* root) {
    		stringstream ss;
    		serialize(root, ss);
    		return ss.str();
    	}
    
    	// Decodes your encoded data to tree.
    	TreeNode* deserialize(string data) {
    		if (data.empty()) return nullptr;
    		int pos = 0;
    		return deserialize(data, pos);
    	}
    };

Log in to reply
 

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