Succint encoding: serializing shape and values separately (C++, 26 ms)


  • 0
    D

    This simple and fast approach serializes the shape of the tree and the values in the tree using two separate calls. The binary version of this encoding (using 1 bit per node and one word per value) achieves the optimal space bound for large random trees (2 bits per node is optimal because because there are 4^n trees with n nodes). Time is 26 ms, currently in top 10% of runtimes.

    class Codec {
    public:
        void serializeShape(TreeNode* root, ostringstream& s) {
            if (!root) {
                s << '0';
            } else {
                s << '1';
                serializeShape(root->left,  s);
                serializeShape(root->right, s);
            }
        }
        
        void serializeValues(TreeNode* root, ostringstream& s) {
            if (!root) return;
            s << ' ' << root->val;
            serializeValues(root->left,  s);
            serializeValues(root->right, s);
        }
        
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            ostringstream stream;
            serializeShape(root, stream);
            serializeValues(root, stream);
            return stream.str();
        }
    
        void deserializeShape(TreeNode*& root, istringstream& s) {
            char c;
            s.get(c);
            if (c == '1') {
                root = new TreeNode(0);
                deserializeShape(root->left, s);
                deserializeShape(root->right, s);
            }
        }
        
        void deserializeValues(TreeNode* root, istringstream& s) {
            if (!root) return;
            s >> root->val;
            deserializeValues(root->left, s);
            deserializeValues(root->right, s);
        }
        
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            istringstream stream(data);
            TreeNode* root = nullptr;
            deserializeShape(root, stream);
            deserializeValues(root, stream);
            return root;
        }
    };
    

Log in to reply
 

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