247. Serialize and Deserialize N-ary Tree

Serialize using preorder DFS, recording each node's value followed by its child count. This uniquely defines the tree structure.

Approach

1. Serialize: DFS preorder, for each node write value and number of children.
2. Deserialize: Read tokens and recursively reconstruct children.

Complexity

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

import java.util.*;

class Codec {
    public String serialize(Node root) {
        if (root == null) return "";
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.toString().trim();
    }

    private void dfs(Node node, StringBuilder sb) {
        sb.append(node.val).append(" ");
        sb.append(node.children.size()).append(" ");
        for (Node child : node.children) {
            dfs(child, sb);
        }
    }

    public Node deserialize(String data) {
        if (data == null || data.isEmpty()) return null;
        Iterator<String> tokens = Arrays.asList(data.split(" ")).iterator();
        return build(tokens);
    }

    private Node build(Iterator<String> tokens) {
        int val = Integer.parseInt(tokens.next());
        int count = Integer.parseInt(tokens.next());
        Node node = new Node(val, new ArrayList<>());
        for (int i = 0; i < count; i++) {
            node.children.add(build(tokens));
        }
        return node;
    }
}