428. Serialize and Deserialize N-ary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following 3-ary tree

as [1 [3[5 6] 2 4]]. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note:

1. N is in the range of [1, 1000]

2. Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

class Node {
public:
    int val = NULL;
    vector<Node*> children;

    Node() {}

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

// Preorder Recursion
void serialize(Node* root, ostringstream& os) {
    if (!root) {
        os << "# ";
    } else {
        os << to_string(root->val) << " " << to_string(root->children.size()) << " ";
        for (Node*& child : root->children) {
            serialize(child, os);
        }
    }
}
// Encodes a tree to a single string.
string serialize(Node* root) {
    ostringstream os;
    serialize(root, os);
    return os.str();
}

Node* deserialize(istringstream& is) {
    string val, size;
    is >> val;
    if (val == "#") return nullptr;
    is >> size;
    Node* res = new Node(stoi(val), {});
    for (int i = 0; i < stoi(size); ++i) {
        res->children.push_back(deserialize(is));
    }
    return res;
}
// Decodes your encoded data to tree.
Node* deserialize(string data) {
    istringstream is(data);
    return deserialize(is);
}

// Level Order Traversal
// Encodes a tree to a single string.
string serialize(Node* root) {
    if (!root) return "#";
    string res;
    queue<Node*> q{{root}};
    while (!q.empty()) {
        Node *t = q.front(); q.pop();
        res += to_string(t->val) + " " + to_string(t->children.size()) + " ";
        for (Node *child : t->children) {
            q.push(child);
        }
    }
    return res;
}

// Decodes your encoded data to tree.
Node* deserialize(string data) {
    istringstream iss(data);
    queue<Node*> qNode;
    queue<int> qSize;
    string val = "", size = "";
    iss >> val;
    if (val == "#") return NULL;
    iss >> size;
    Node *res = new Node(stoi(val), {}), *cur = res;
    qNode.push(cur);
    qSize.push(stoi(size));
    while (!qNode.empty()) {
        Node *t = qNode.front(); qNode.pop();
        int len = qSize.front(); qSize.pop();
        for (int i = 0; i < len; ++i) {
            if (!(iss >> val)) break;
            if (!(iss >> size)) break;
            cur = new Node(stoi(val), {});
            qNode.push(cur);
            qSize.push(stoi(size));
            t->children.push_back(cur);
        }
    }
    return res;
}