26ms Simple C++ Solution - use lower_bound to deserialize the preorder string.


  • 1
    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            stringstream ss;
            preorder(root, ss);
            return ss.str();
        }
        
        void preorder(TreeNode* root, stringstream& ss) {
            if (root != nullptr) {
                ss << root->val << ' ';
                preorder(root->left, ss);
                preorder(root->right, ss);
            }
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            int n = count(data.begin(), data.end(), ' ');
            vector<int> nums(n);
            stringstream ss(data);
            for (int i = 0; i < n; ++i) {
                ss >> nums[i];
            }
            
            return buildTree(nums.begin(), nums.end());
        }
        
        TreeNode* buildTree(vector<int>::iterator begin, vector<int>::iterator end) {
            if (begin == end) {
                return nullptr;
            }
            
            auto node = new TreeNode(*begin);
            
            auto itor = lower_bound(begin + 1, end, *begin);
            
            node->left = buildTree(begin + 1, itor);
            node->right = buildTree(itor, end);
            
            return node;
        }
    };
    

  • 0
    G

    I have a similar solution. But I don't know why it takes about 45ms.

    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);
        }
        
        TreeNode* deserialize(vector<int>::iterator first, vector<int>::iterator last) {
            if (first == last) return nullptr;
            TreeNode* root = new TreeNode(*first);
            auto it = upper_bound(first + 1, last, *first);
            root -> left = deserialize(first + 1, it);
            root -> right = deserialize(it, last);
            return root;
        }
        
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            istringstream iss(data);
            vector<int> vals;
            int val;
            while (iss >> val) vals.push_back(val);
            return deserialize(vals.begin(), vals.end());
        }
    };
    

  • 0
    D

    @garygao1993 The runtimes provided by OJ are not absolute. I say this following my observations wherein same solution submitted back to back produces varying runtimes in chart.


  • 0

    @garygao1993
    I guess vals.push_back(val); is too slow for a huge array (tree).


  • 1

    I guess vals.push_back(val); is too slow for a huge array (tree).

    The difference of solutions between @Hunter37 and @garygao1993 is that @Hunter37 allocated exact space for vector<int> nums(n) in the first place while @garygao1993 dynamically pushed values to the vector one by one.

    In C++ std::vector, it is always a good practice to allocate enough space for vectors before hand if you already know exactly how much space you will need. The memory allocation behind the scene is that vector will only double its length when pushing new elements into vector only if there isn't enough. However, due to the contiguous memory allocation of vector, it needs to find another bigger memory block and copy the existing values to the new location.

    It is similar to this situation: if you are allowed to use only one box (i.e., contiguous memory) to hold all your books, it is better to do a count before you start packing with a random size box, which could save you the trouble to move books from one box to a bigger one just in case the current box isn't large enough.


Log in to reply
 

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