⚡Flashcard Drill➔
NeetCode #414LC-428HardTreesNC Algo100
← Back to All Problems

#414 · #428 · Serialize and Deserialize N-ary Tree(序列化和反序列化 N 叉树)

📌 Problem Statement & Constraints

Design an algorithm to serialise and deserialise an N-ary tree. Constraints: the number of nodes is in [0, 10^4], 0 <= Node.val <= 10^4, the depth is at most 1000.

💡 Core Algorithmic Approaches

  1. A pre-order traversal with an explicit child count per node is unambiguous.
  2. Serialise each node as <value>,<child count> followed by its children's encodings.
  3. Deserialise by consuming the tokens in the same order: read the value and the child count, then recursively build that many children.
  4. The child count is what replaces the null markers used in the binary-tree version.

💻 Benchmark Python3 Implementation

class Codec:
    def serialize(self, root: "Optional[Node]") -> str:
        if not root:
            return ""
        parts = []

        def dfs(node: "Node") -> None:
            parts.append(str(node.val))
            parts.append(str(len(node.children)))   # child count disambiguates
            for c in node.children:
                dfs(c)

        dfs(root)
        return ",".join(parts)

    def deserialize(self, data: str) -> "Optional[Node]":
        if not data:
            return None
        tokens = iter(data.split(","))

        def build() -> "Node":
            val = int(next(tokens))
            n = int(next(tokens))                   # how many children follow
            node = Node(val, [])
            for _ in range(n):
                node.children.append(build())
            return node

        return build()

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) for both directions.
💾 Space Complexity
O(n) for the token list plus O(h) for the recursion.

⚠️ Interview Pitfalls & Follow-ups

  • Omitting the child count: the structure would be ambiguous, since an N-ary tree has no null markers between siblings.
  • Using a fixed-width encoding: values are not bounded in length, so a delimiter is required.
  • Consuming tokens out of order: the recursion must share a single iterator so the pre-order sequence is respected.
  • Recursing on a depth-1000 tree: within Python's default limit, but a stack-based version would be safer.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems