Coder's Cat

LeetCode: Serialize and Deserialize N-ary Tree

2020-08-01

Solution for LeetCode challenge: Serialize and Deserialize N-ary Tree

file:img/CAPTURE-2020_08_01_leetcode-serialize-and-deserialize-n-ary-tree.org_20200801_202436.png

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;
};

Preparing for an interview? Check out this!