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

• 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) {
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) {
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);
}
}
};
``````

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

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

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