Serialize and deserialize a trie (prefix tree, search on internet for more details).

You can specify your own serialization algorithm, the online judge only cares about whether you can successfully deserialize the output from your own serialize function.

Notice

You don't have to serialize like the test data, you can design your own format.

Have you met this question in a real interview?

Yes

Example

str = serialize(old_trie)

>
>
 str can be anything to represent a trie
new_trie = deserialize(str)

>
>
 new_trie should have the same structure and values with old_trie

An example of test data: trie tree<a<b<e<>>c<>d<f<>>>>, denote the following structure:

     root
      /
     a
   / | \
  b  c  d
 /       \
e         f

/**
 * Definition of TrieNode:
 * 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
        string res;
        if (root == NULL) {
            return res;
        }
        for (auto& node : root->children) {
            res += node.first;
            res += serialize(node.second);
        }
        res = "<" + res + ">";
        // cout << res << endl;
        return res;
    }

    /**
     * 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
        if (data.empty()) {
            return NULL;
        }
        TrieNode* root = new TrieNode();
        TrieNode* current = root;
        stack<TrieNode*> st;
        int len = data.length();
        for (int i = 0; i < len; ++i) {
            if (data[i] == '<') {
                st.push(current);
            } else if (data[i] == '>') {
                st.pop();
            } else {
                current =  new TrieNode();
                st.top()->children[data[i]] = current;
            }
        }

        return root;
    }
};