C++_29ms_69.25%_AC


  • 0

    Basic idea is first convert BST to string by preorder traverse, because the inorder traverse of BST is ordered, so we can convert the preorder to inorder via sorting the vector.

    And then, we can build BST via preorder and inorder.

    class Codec {
    public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res = "";
        stack<TreeNode*> s;
        if(root) s.push(root);
        while(!s.empty()){
            TreeNode* tmp = s.top();
            s.pop();
            //RIGHT, then LEFT
            if(tmp->right) s.push(tmp->right);
            if(tmp->left) s.push(tmp->left);
            res += to_string(tmp->val) +' ';
        }
        return res;
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty()) return nullptr;
        TreeNode* root;
        vector<int> preorder;
        for(int i = 0; i < data.size(); ++i){
            int sign = 1;
            int value = 0;
            if(data[i] == ' ') continue;
            if(data[i] == '-'){sign = -1; i++;}
            while(data[i] != ' '){
                value = value*10 + data[i] - '0';
                i++;
            }
            preorder.push_back(value * sign);
        }
        
        vector<int> inorder = preorder;
        sort(inorder.begin(), inorder.end());
        int n = inorder.size();
        root = buildBST(preorder,inorder, 0, n-1, 0, n-1);
        return root;
    }
    
    TreeNode* buildBST(vector<int>& preorder, vector<int>& inorder,int ps, int pe, int is, int ie){
        if(ps > pe || is > ie) return nullptr;
        int r = preorder[ps];
        TreeNode* root = new TreeNode(r);
        int index = 0;
        // O(n) for search
        //for(int i = is; i <= ie; ++i){
        //    if(inorder[i] == r){index = i; break;}
        //}
        //O(log n) by Binary Search
        int left = is, right = ie;
        while(left <= right){
            int m = (right + left)>>1;
            if(inorder[m] < r){left = m + 1;}
            else if(inorder[m] > r){right = m - 1;}
            else{index = m; break;}
        }
        root->left = buildBST(preorder, inorder, ps + 1, ps + index - is, is, index-1);
        root->right = buildBST(preorder, inorder, ps + index - is + 1, pe, index+1, ie);
        return root;
    }
    };
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec;
    // codec.deserialize(codec.serialize(root));
    

    0_1480468610448_71E87E90-0AAB-4B66-A936-FAAD505B0DDC.png


Log in to reply
 

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