12-liner using preorder

  • 0


    1. Pre-order and In-order traversals can uniquely determine a binary tree.
    2. The in-order of any BST must be sorted.
    3. No need to use any symbol to represent NULL node. (this is why BST serialization is more compact than generic binary tree)
        string serialize(TreeNode* r) {
            if (!r) return "";
            return to_string(r->val) + " " + serialize(r->left) + serialize(r->right);
        TreeNode* deserialize(string data) {
            vector<int> preorder;
            stringstream ss(data);
            for (string s; ss >> s;) preorder.push_back(stoi(s));   
            return buildTree(preorder.begin(), preorder.end());
        // s: preorder start; e: preorder end
        TreeNode* buildTree(vector<int>::iterator s, vector<int>::iterator e) {
            if (s == e) return nullptr;                        
            auto i = upper_bound(s+1, e, *s);
            auto r = new TreeNode(*s);
            r->left  = buildTree(s+1, i); 
            r->right = buildTree(i, e);
            return r;

Log in to reply

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