Extremely Fast and Simple C++ Solution (Beat 99.77%)


  • 1
    W

    For serialize:
    Traverse the tree in preorder to serialize it. The key is to differentiate leaf node and non-leaf node. Every time when we encounter a non-leaf node, we use a space character to denote it and recursively serialize its left child and right child. If the node is a leaf, we just don't do any thing.
    For deserialize
    With the logic of serialization in mind, we can devise algorithm for deserialization. Remember that I did not create extra characters for a leaf node, and I use a space character to denote the non-leaf node. So every time when we create a node, we must check if it is a leaf node or not. If the next character following the number is not a space character, we know it is a leaf node, we stop recursion. If it is a non-leaf node, we must recursively build the left subtree and right subtree for this node. Every time when we enter a new recursion, we either see a new number (either positive or negative) or see a ',', which denotes that the left child of node in parent recursion call is a NULL, so we just return NULL.

    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            if(root == NULL) return "";
            ostringstream os;
            serialHelper(root, os);
            return os.str();
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            if(data.empty()) return NULL;
            int pos = 0;
            return build(data, pos);
        }
        
    private:
        void serialHelper(TreeNode* node, ostringstream& os) {
            if(node == NULL) return;
            os << node->val;
            if(node->left || node->right) {
                os << ' ';
                serialHelper(node->left, os);
                os << ',';
                serialHelper(node->right, os);
            }
        }
    
        TreeNode* build(string& data, int& pos) {
            int sign = 1, val = 0;
            if(data[pos] == '-') { // If this is a negative number, record it.
                sign = -1;
                pos++;
            }
            if(isdigit(data[pos])) {
                while(isdigit(data[pos])) {
                    val = val * 10 + (int)(data[pos] - '0');
                    pos++;
                }
                TreeNode* newnode = new TreeNode(val*sign);
                if(data[pos] == ',') { // This is a leaf node.
                    pos++;
                    return newnode;
                }
                else { // data[pos] == ' '. This is not a leaf node. Build its left child and right child.
                    pos++;
                    newnode->left = build(data, pos);
                    newnode->right = build(data, pos);
                    return newnode;
                }
            }
            else { // data[pos] == ','. This happens when left child of parent node is NULL.
                pos++;
                return NULL;
            }
            
        }
    };
    

    I also generalize my solution for a N-way Trie, with the following trie node struct:

    class TrieNode {
    	public:
    		TrieNode() {}
    		map<char, TrieNode*> children;
    };
    
    class Solution {
    public:
        /**
         * This method will be invoked first, you should design your own algorithm 
         * to serialize a trie which denote by a root node to a string which
         * can be easily deserialized by your own "deserialize" method later.
         */
        string serialize(TrieNode* root) {
            // Write your code here
            ostringstream os;
            char c = 'a';
            serialHelper(c, root, os);
            return os.str();
        }
    
        /**
         * This method will be invoked second, the argument data is what exactly
         * you serialized at method "serialize", that means the data is not given by
         * system, it's given by your own serialize method. So the format of data is
         * designed by yourself, and deserialize it here as you serialize it in 
         * "serialize" method.
         */
        TrieNode* deserialize(string data) {
            // Write your code here
            int pos = 0;
            auto p = build(data, pos);
            return p.second;
        }
        
    private:
        void serialHelper(char c, TrieNode* node, ostringstream& os) {
            if(node == NULL) return;
            os << c;
            if(!node->children.empty()) {
                os << '[';
                for(auto& p: node->children) {
                    serialHelper(p.first, p.second, os);
                }
                os << ']';
            }
        }
        
        pair<char, TrieNode*> build(string& data, int& pos) {
            if(isalpha(data[pos])) {
                TrieNode* newnode = new TrieNode();
                char c = data[pos++];
                if(pos == data.size() || data[pos] != '[') {
                    return make_pair(c, newnode);
                }
                else {
                    pos++;
                    while(data[pos] != ']') {
                        auto p = build(data, pos);
                        if(p.second != NULL) newnode->children[p.first] = p.second;
                    }
                    pos++;
                    return make_pair(c, newnode);
                }
            }
            else {
                pos++;
                return make_pair('#', nullptr);
            }
        }
    };
    

  • 0
    H

    I copy-pasted your code and only get 33%. did you really get 99.77%?


  • 0
    W

    @henrywu2016 I don't know what happened in the testing. I run 10 times, I got 1 time 33%, 9 times 99%


Log in to reply
 

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