Preorder serialize and recursive deserialize C++ 26ms

  • 3
    class Codec {
        //Encodes a tree to a single string.
        void serialize(TreeNode* root, vector<int> &val)
            if(root == NULL) return;
            serialize(root->left, val);
            serialize(root->right, val);
        string serialize(TreeNode* root) {
            vector<int> val;
            serialize(root, val);
            char *p = (char*);
            string str(p, val.size() * sizeof(int));
            return str;
        // deserialize val[l .. r]
        TreeNode* deserializeSubtree(int *val, int l, int r)
            if(l > r) return NULL;
            TreeNode *subRoot = new TreeNode(val[l]);
            int i = l+1;
            while(i <= r && val[i] < val[l]) ++i; 
            subRoot->left = deserializeSubtree(val, l+1, i-1);
            subRoot->right = deserializeSubtree(val, i, r);
            return subRoot;
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            //preorder traversed string
            int n = data.size() / sizeof(int);
            TreeNode *root = deserializeSubtree((int*), 0, n-1);
            return root;

  • 0

    @freeprogrammer very good solution of C++ cast. so we don't need INT_MIN and INT_MAX to be boundary

  • 0

    What is complexity of this solution?
    O(N^2) ?

Log in to reply

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