Evolve from bt to bst


  • 0
    1. O(n) reuse Serialize and Deserialize Binary Tree. Preorder traversal to encode and decode. Add '#' to mark termination.
        string serialize(TreeNode* root) {
            ostringstream ss;
            serialize(root,ss);
            return ss.str();
        }
        TreeNode* deserialize(string data) {
            istringstream ss(data);
            return deserialize(ss);
        }
        void serialize(TreeNode *r, ostringstream& ss) {
            if(r) {
                ss<<r->val<<" ";
                serialize(r->left,ss);
                serialize(r->right,ss);
            } else ss<<"# ";
        }
        TreeNode* deserialize(istringstream& ss) {
            string val;
            ss>>val;
            if(val == "#") return NULL;
            TreeNode *r = new TreeNode(stoi(val));
            r->left = deserialize(ss);
            r->right = deserialize(ss);
            return r;
        }
    
    1. O(n) Preorder traversal without terminator. We should be able to do better than bt by using bst property. The problem description mentions the encoded string should be as compact as possible. This hints for the removal of terminators. Since the left subtree is smaller than the root, the left subtree terminates if we see a value larger than root. INT_MAX is used as the initial upper bound. If the tree has INT_MAX, then it is either root or in a right subtree. Terminating condition is num>INT_MAX, so in both cases the node is decoded correctly. This problem assumes no duplicates in bst. If there are, then we need to know whether duplicates branches to the left or right. The corresponding terminating condition is num > up or num >= up. There could be more corner cases...
        TreeNode* deserialize(string data) {
            istringstream ss(data);
            return deserialize(INT_MAX, ss);
        }
        void serialize(TreeNode *r, ostringstream& ss) {
            if(!r) return;
            ss<<r->val<<" ";
            serialize(r->left,ss);
            serialize(r->right,ss);
        }
        TreeNode* deserialize(int up, istringstream& ss) {
            string val;
            auto pos = ss.tellg(); //cache current position
            ss>>val;
            if(val == "") return NULL;
            int num = stoi(val);
            if( num > up) {
                ss.seekg(pos); //roll back ss
                return NULL;
            }
            TreeNode *r = new TreeNode(num);
            r->left = deserialize(num, ss);
            r->right = deserialize(up, ss);
            return r;
        }
    

Log in to reply
 

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