C++ 23ms beat 98% using binary format


  • 0
    M

    this solution use string as bytes-array instead of char-array, so it saves time on number-parsing.
    we can use INT_MIN as escaping-number:
    (INT_MIN, INT_MIN) stands for number INT_MIN
    (INT_MIN, 0) stands for a null-tree-node

    class Codec {
    public:
        void to_buf(string& buf, TreeNode* root)
        {
            if (!root)
            {
                buf += string(2 * sizeof(int), 0);
                int tmp = INT_MIN;
                memcpy(&buf[buf.size() - 2 * sizeof(int)], &tmp, sizeof(int));
                tmp = 0;
                memcpy(&buf[buf.size() - 1 * sizeof(int)], &tmp, sizeof(int));
            }
            else
            {
                if (root->val == INT_MIN)
                { 
                    buf += string(2 * sizeof(int), 0);
                    memcpy(&buf[buf.size() - 2 * sizeof(int)], &(root->val),  sizeof(int));
                    memcpy(&buf[buf.size() - 1 * sizeof(int)], &(root->val),  sizeof(int));
                }
                else
                {
                    buf += string(1 * sizeof(int), 0);
                    memcpy(&buf[buf.size() - 1 * sizeof(int)], &(root->val), sizeof(int));
                }
                to_buf(buf, root->left);
                to_buf(buf, root->right);
            }
        }
    
        TreeNode* from_buf(int*& buf)
        {
            if (*buf == INT_MIN)
            {
                ++buf;
                if (*buf == 0)
                {
                    ++buf;
                    return NULL;
                }
            }
            TreeNode* res = new TreeNode(*buf);
            ++buf;
            res->left = from_buf(buf);
            res->right = from_buf(buf);
            return res;
        }
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            string res;
            to_buf(res, root);
            return res;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            int* ptr = (int*)&data[0];
            return from_buf(ptr);
        }
    };
    

    };


Log in to reply
 

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