Clean C++ solution


  • 41
    D
    class Codec {
    public:
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            if (root == nullptr) return "#";
            return to_string(root->val)+","+serialize(root->left)+","+serialize(root->right);
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            return mydeserialize(data);
        }
        TreeNode* mydeserialize(string& data) {
            if (data[0]=='#') {
                if(data.size() > 1) data = data.substr(2);
                return nullptr;
            } else {
                TreeNode* node = new TreeNode(helper(data));
                node->left = mydeserialize(data);
                node->right = mydeserialize(data);
                return node;
            }
        }
    private:
        int helper(string& data) {
            int pos = data.find(',');
            int val = stoi(data.substr(0,pos));
            data = data.substr(pos+1);
            return val;
        }
    };`

  • 10
    X

    Using stringstream will make your code extremely short

    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            if (root == NULL) return "#";
            return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
        }
    
        TreeNode* deserialize(string data) {
            if (data == "#") return NULL;
            stringstream s(data);
            return makeDeserialize(s);
        }
        
        TreeNode* makeDeserialize(stringstream& s) {
            string str;
            getline(s, str, ',');
            if (str == "#") {
                return NULL;
            } else {
                TreeNode* root = new TreeNode(stoi(str));
                root->left = makeDeserialize(s);
                root->right = makeDeserialize(s);
                return root;
            }
        }
    };

  • 0
    I

    Using another reference variable to record the current position is more efficient because data.substr(pos+1) in your helper function could be inefficient.

    Using stringstream mentioned by xiaohui5319 is another good choice.

    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            if (!root) return "#";
            return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            int pos = 0;
            return myDeserialize(data, pos);
        }
        
        TreeNode* myDeserialize(string& data, int& pos) {
            if (pos < data.length() && data[pos] == '#') {
                pos += 2;
                return NULL;
            }
            
            int delimiterPos = data.find(',', pos);
            int length = delimiterPos - pos;
            int value = stoi(data.substr(pos, length));
            TreeNode* root = new TreeNode(value);
            pos += length + 1;
            root->left = myDeserialize(data, pos);
            root->right = myDeserialize(data, pos);
            return root;
        }
    };
    

Log in to reply
 

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