# Be creative! Share my C++ solution.

• The problem asks me to be creative, so I came up this idea.

For tree,

``````    1
/ \
2   3
/ \
4   5
/     \
6       7
``````

The serialization will be `1,2,N,3,4,5,L,6,R,7,N,N`

• `N` represents there are no children for the previous node.
• `L` represents that the previous node have one left child, and the value of that child comes after it.
• `R` represents that there is one right child.

I use queue to do level traversal, the time complexity should be O(n) for both operations.

C++ code here:

``````class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
if (root == NULL) return "";
queue<TreeNode *> q;
q.push(root);
TreeNode *p;
string result = to_string(root->val);
while (!q.empty()) {
p = q.front();
q.pop();
if (p->left && p->right) {
q.push(p->left);
q.push(p->right);
result += "," + to_string(p->left->val) + "," + to_string(p->right->val);
}
else if (p->left && !p->right) {
q.push(p->left);
result += ",L," + to_string(p->left->val);
}
else if (!p->left && p->right) {
q.push(p->right);
result += ",R," + to_string(p->right->val);
}
else {
result += ",N";
}
}
return result;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
if (data.length() == 0) return NULL;
vector<string> nodes = split(data, ',');
auto it = nodes.begin();
TreeNode *root = new TreeNode(stoi(*(it++)));
queue<TreeNode *> q;
q.push(root);
while (!q.empty() && it != nodes.end()) {
TreeNode *p = q.front();
if (*it == "N") {
it++;
}
else if (*it == "L") {
p->left = new TreeNode(stoi(*(++it)));
it++;
}
else if (*it == "R") {
p->right = new TreeNode(stoi(*(++it)));
it++;
}
else {
p->left = new TreeNode(stoi(*(it++)));
p->right = new TreeNode(stoi(*(it++)));
}

q.pop();
if (p->left) q.push(p->left);
if (p->right) q.push(p->right);
}
return root;
}

vector<string> split(string str, char delimiter) {
vector<string> result;
int last = 0;
for (int i = 0; i <= str.length(); i++) {
if (str[i] == delimiter || str[i] == '\0') {
result.push_back(str.substr(last, i - last));
last = i + 1;
}
}
return result;
}
};``````

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