428. Serialize and Deserialize N-ary Tree

• Time: $O(n)$
• Space: $O(n)$

C++JavaPython

class Codec {
 public:
  // Encodes a tree to a single string.
  string serialize(Node* root) {
    if (root == nullptr)
      return "";

    string s;
    queue<Node*> q{{root}};
    s += to_string(root->val) + " ";

    while (!q.empty())
      for (int sz = q.size(); sz > 0; --sz) {
        Node* node = q.front();
        q.pop();
        if (node->children.empty()) {
          s += "n";
        } else {
          for (Node* child : node->children) {
            q.push(child);
            s += to_string(child->val) + "#";
          }
        }
        s += " ";
      }

    return s;
  }

  // Decodes your encoded data to tree.
  Node* deserialize(string data) {
    if (data.empty())
      return nullptr;

    istringstream iss(data);
    string word;
    iss >> word;
    Node* root = new Node(stoi(word));
    queue<Node*> q{{root}};

    while (iss >> word) {
      Node* parent = q.front();
      q.pop();
      vector<Node*> children;
      for (const string& kid : getKids(word)) {
        if (kid == "n")
          continue;
        Node* child = new Node(stoi(kid));
        children.push_back(child);
        q.push(child);
      }
      parent->children = children;
    }

    return root;
  }

 private:
  vector<string> getKids(const string& word) {
    vector<string> kids;
    for (int i = 0, j = 0; j < word.length(); ++j)
      if (word[j] == '#') {
        kids.push_back(word.substr(i, j - i));
        i = j + 1;
      }
    return kids;
  }
};

class Codec {
  // Encodes a tree to a single string.
  public String serialize(Node root) {
    if (root == null)
      return "";

    StringBuilder sb = new StringBuilder().append(root.val).append(",");
    Queue<Node> q = new ArrayDeque<>(Arrays.asList(root));

    while (!q.isEmpty())
      for (int sz = q.size(); sz > 0; --sz) {
        Node node = q.poll();
        if (node.children.isEmpty()) {
          sb.append("n");
        } else {
          for (Node child : node.children) {
            q.offer(child);
            sb.append(child.val).append("#");
          }
        }
        sb.append(",");
      }

    return sb.toString();
  }

  // Decodes your encoded data to tree.
  public Node deserialize(String data) {
    if (data.equals(""))
      return null;

    final String[] vals = data.split(",");
    Node root = new Node(Integer.parseInt(vals[0]));
    Queue<Node> q = new ArrayDeque<>(Arrays.asList(root));

    for (int i = 1; i < vals.length; ++i) {
      Node parent = q.poll();
      List<Node> children = new ArrayList<>();
      for (final String kid : vals[i].split("#")) {
        if (kid.equals("n"))
          continue;
        Node child = new Node(Integer.parseInt(kid));
        children.add(child);
        q.offer(child);
      }
      parent.children = children;
    }

    return root;
  }
}

class Codec:
  def serialize(self, root: 'Node') -> str:
    """Encodes a tree to a single string."""
    if not root:
      return ''

    s = []
    q = collections.deque([root])
    s.append(str(root.val) + ' ')

    while q:
      for _ in range(len(q)):
        node = q.popleft()
        if not node.children:
          s.append('n')
        else:
          for child in node.children:
            q.append(child)
            s.append(str(child.val) + '#')
        s.append(' ')

    return ''.join(s)

  def deserialize(self, data: str) -> 'Node':
    """Decodes your encoded data to tree."""
    if not data:
      return None

    words = data.split()
    root = Node(int(words[0]))
    q = collections.deque([root])

    for word in words[1:]:
      parent = q.popleft()
      children = []
      for kid in word.split('#'):
        if kid in ('', 'n'):
          continue
        child = Node(int(kid))
        children.append(child)
        q.append(child)
      parent.children = children

    return root