We use format: “val child_size children …”. And in deserialize
procedure, we use a depth first search
to recursive construct a new tree.
Note: store the current position, just as a file stream.
Solution
class Codec {
public:
// Encodes a tree to a single string.
string serialize(Node* root) {
string s;
if (!root) return "#";
s = to_string(root->val) + " " + to_string(root->children.size());
for (int i = 0; i< root->children.size(); i++)
s = s + " " + serialize(root->children[i]);
return s;
}
// Decodes your encoded data to tree.
Node* deserialize(string data) {
cur = 0;
return dfs(data);
}
int try_get_val(string& str, int& pos) {
int val = 0;
while(pos < str.size()) {
char c = str[pos];
if(c >= '0' && c <= '9') {
val = val * 10 + (c - '0');
pos++;
} else break;
}
pos++; // skip next ' '
return val;
}
Node* dfs(string& str) {
if (str[cur] == '#') return NULL;
int val = try_get_val(str, cur);
int size = try_get_val(str, cur);
Node *node = new Node(val);
for (int i = 0; i < size; ++i)
node->children.push_back(dfs(str));
return node;
}
int cur;
};
The post LeetCode: Serialize and Deserialize N-ary Tree appeared first on Coder's Cat.
Top comments (0)