C++_queue + vector_use Heap to find child node_35ms_92.74%_Accepted!!!!


  • 0

    OMG, this problem costed me 3 hours.....

    • For serialization, using the queue to store each tree node, and use the n to count the number of tree nodes in this level. (Very similar like the Level-traverse of the binary tree).

    • For deserialization, using the vector to store each tree node. Then use the heap to find out the children nodes of each parent node. One more thing you should be aware is that if there is negative value in the node.

    Code:

    class Codec {
    public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root == NULL) return "[]";
        string res = "[";
        queue<TreeNode*> Q;
        Q.push(root);
        while(!Q.empty()){
            int n = Q.size();
            int allEmpty = 0;
            while(n > 0){
                TreeNode* tmp = Q.front();
                Q.pop();
                n--;
                if(tmp != NULL){
                    Q.push(tmp->left); Q.push(tmp->right); res += to_string(tmp->val);
                    allEmpty = (tmp->left != nullptr) || (tmp->right != nullptr) || (allEmpty != 0);
                }
                else{res += "null";}
                res += ",";
            }
            if(allEmpty == 0) break;
        }
        
        if(res[res.size()-1] == ','){res.pop_back();}
        res += "]";
        return res;
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty() || data == "[]") return nullptr;
        int n = data.size() - 1, i = 1; //ignore the first "[" and "]""
        vector<TreeNode*> Q;
        int sign = 1;
        
        while(i < n){
            if(isdigit(data[i])){
                int sum = 0;
                while(i < n && isdigit(data[i])){
                    sum = sum * 10 + (data[i] - '0');
                    ++i;
                }
                Q.push_back(new TreeNode(sum*sign));
                sign = 1;
            }else if(data[i] == 'n'){
                i = i + 4;
                Q.push_back(nullptr);
            }else if(data[i] == '-'){
                sign = -1;
                ++i;
            }else{
                ++i;
            }
        }
        
        if(Q.size() == 1) return Q[0];
        for(int i = 0, k = 0; k <= Q.size()/2 - 1 && i < n; ++i, ++k){
            if(Q[i] != nullptr){
                Q[i]->left = Q[k*2+1];
                if(k*2+2 > Q.size()) break;
                Q[i]->right = Q[k*2+2];
            }else{
                while(Q[i] == nullptr){++i;}
                Q[i]->left = Q[k*2+1];
                if(k*2+2 > Q.size()) break;
                Q[i]->right = Q[k*2+2];
            }
        }
        return Q[0];
    }
    };
    

    // Your Codec object will be instantiated and called as such:
    // Codec codec;
    // codec.deserialize(codec.serialize(root));

    Time
    0_1476148186718_E5A23F6B-49AD-4424-82CA-B2B2F3AEA209.png


Log in to reply
 

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