💬 Discord
Sign In
NeetCode #474LC-297HardTreesBlind 75NC 150NC 250
← Back to All Problems

#474 · #297 · Serialize and Deserialize Binary Tree(二叉树的序列化与反序列化)

📌 Problem Statement & Constraints

Design an algorithm to serialise a binary tree into a string and deserialise that string back into the original tree. Constraints: the number of nodes is in [0, 10^4], -1000 <= Node.val <= 1000.

💡 Core Algorithmic Approaches

  1. A pre-order traversal with an explicit null marker is unambiguous: the structure is recoverable because nulls record where subtrees end.
  2. Serialise by emitting each value or # for None, joined by a delimiter.
  3. Deserialise by consuming tokens in the same pre-order sequence, creating a node and recursing for its children.
  4. The delimiter is essential; without it, multi-digit values would run together.

💻 Benchmark Python3 Implementation

class Codec:
    def serialize(self, root: Optional[TreeNode]) -> str:
        out = []

        def dfs(node: Optional[TreeNode]) -> None:
            if not node:
                out.append("#")            # explicit null marker
                return
            out.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

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

    def deserialize(self, data: str) -> Optional[TreeNode]:
        tokens = iter(data.split(","))

        def build() -> Optional[TreeNode]:
            v = next(tokens)
            if v == "#":
                return None
            node = TreeNode(int(v))
            node.left = build()            # pre-order: left subtree next
            node.right = build()
            return node

        return build()

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n) for both directions: each node emits or consumes one token.
💾 Space Complexity
O(n) for the token list and O(h) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Omitting the null markers: the structure would be ambiguous -- [1, 2] and [1, null, 2] serialise identically.
  • Omitting the delimiter: 12 and 1, 2 would be indistinguishable.
  • Using an index-based iterator instead of a shared iterator: the recursion must consume tokens in a single global order, so a shared iter is the clean way.
  • Serialising with in-order: it does not uniquely determine the tree, so pre-order (or post-order) with nulls is required.