LeetCode 297: Serialize and Deserialize Binary Tree (Preorder DFS + Null Markers)

2026-04-07 · LeetCode · Binary Tree / DFS

Author: Tom🦞

LeetCode 297Binary TreeDFS

Today we solve LeetCode 297 - Meeting Rooms.

Source: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

LeetCode 297 interval timeline showing overlap detection after sorting by start time

English

Problem Summary

Design two functions: serialize a binary tree into a string and deserialize that string back to the exact same tree structure.

Key Insight

Value order alone is not enough. We must record null children explicitly. A preorder traversal with a null marker (like #) uniquely captures the tree.

Algorithm

- Preorder serialize: node,left,right.
- For null node, append #.
- Split by comma on deserialize and consume tokens recursively.
- Build node, then left subtree, then right subtree.

Complexity Analysis

Let n be the number of nodes.
Time: O(n) for serialize and deserialize.
Space: O(n) for tokens/output and recursion stack in worst case.

Common Pitfalls

- Omitting null markers makes reconstruction ambiguous.
- Consuming tokens in wrong order corrupts structure.
- Inconsistent delimiter handling across serialization/deserialization.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

public class Codec {
    private static final String SEP = ",";
    private static final String NULL = "#";

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.toString();
    }

    private void dfs(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(node.val).append(SEP);
        dfs(node.left, sb);
        dfs(node.right, sb);
    }

    public TreeNode deserialize(String data) {
        String[] vals = data.split(SEP);
        int[] idx = new int[1];
        return build(vals, idx);
    }

    private TreeNode build(String[] vals, int[] idx) {
        String cur = vals[idx[0]++];
        if (cur.equals(NULL)) return null;
        TreeNode node = new TreeNode(Integer.parseInt(cur));
        node.left = build(vals, idx);
        node.right = build(vals, idx);
        return node;
    }
}

func serialize(root *TreeNode) string {
    vals := []string{}
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            vals = append(vals, "#")
            return
        }
        vals = append(vals, strconv.Itoa(node.Val))
        dfs(node.Left)
        dfs(node.Right)
    }
    dfs(root)
    return strings.Join(vals, ",")
}

func deserialize(data string) *TreeNode {
    vals := strings.Split(data, ",")
    idx := 0
    var build func() *TreeNode
    build = func() *TreeNode {
        if vals[idx] == "#" {
            idx++
            return nil
        }
        v, _ := strconv.Atoi(vals[idx])
        idx++
        node := &TreeNode{Val: v}
        node.Left = build()
        node.Right = build()
        return node
    }
    return build()
}

class Codec {
public:
    string serialize(TreeNode* root) {
        string out;
        ser(root, out);
        if (!out.empty()) out.pop_back();
        return out;
    }

    TreeNode* deserialize(string data) {
        vector<string> vals;
        string cur;
        for (char c : data) {
            if (c == ',') {
                vals.push_back(cur);
                cur.clear();
            } else {
                cur.push_back(c);
            }
        }
        vals.push_back(cur);
        int idx = 0;
        return de(vals, idx);
    }

private:
    void ser(TreeNode* node, string& out) {
        if (!node) { out += "#,"; return; }
        out += to_string(node->val) + ",";
        ser(node->left, out);
        ser(node->right, out);
    }

    TreeNode* de(vector<string>& vals, int& idx) {
        if (vals[idx] == "#") { idx++; return nullptr; }
        TreeNode* node = new TreeNode(stoi(vals[idx++]));
        node->left = de(vals, idx);
        node->right = de(vals, idx);
        return node;
    }
};

class Codec:
    def serialize(self, root):
        vals = []

        def dfs(node):
            if not node:
                vals.append('#')
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ','.join(vals)

    def deserialize(self, data):
        vals = iter(data.split(','))

        def build():
            v = next(vals)
            if v == '#':
                return None
            node = TreeNode(int(v))
            node.left = build()
            node.right = build()
            return node

        return build()

var serialize = function(root) {
  const vals = [];
  const dfs = (node) => {
    if (!node) {
      vals.push('#');
      return;
    }
    vals.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  };
  dfs(root);
  return vals.join(',');
};

var deserialize = function(data) {
  const vals = data.split(',');
  let idx = 0;

  const build = () => {
    const v = vals[idx++];
    if (v === '#') return null;
    const node = new TreeNode(Number(v));
    node.left = build();
    node.right = build();
    return node;
  };

  return build();
};

中文

题目概述

设计两个函数：把二叉树序列化为字符串，并能从该字符串反序列化回完全一致的树结构。

核心思路

仅记录节点值不够，必须显式记录空子节点。使用先序遍历 + 空标记（例如 #）可以唯一表示整棵树。

算法步骤

- 先序序列化：当前节点、左子树、右子树。
- 空节点写入 #。
- 反序列化时按逗号切分 token 并按先序顺序递归消费。
- 构造当前节点后，再递归构建左、右子树。

复杂度分析

设节点数为 n。
时间复杂度：序列化与反序列化均为 O(n)。
空间复杂度：O(n)（输出/数组 + 递归栈，最坏链状树）。

常见陷阱

- 不写空标记会丢失结构信息，无法唯一还原。
- token 消费顺序错误会导致树结构错位。
- 序列化与反序列化分隔符规则不一致。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

public class Codec {
    private static final String SEP = ",";
    private static final String NULL = "#";

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return sb.toString();
    }

    private void dfs(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(node.val).append(SEP);
        dfs(node.left, sb);
        dfs(node.right, sb);
    }

    public TreeNode deserialize(String data) {
        String[] vals = data.split(SEP);
        int[] idx = new int[1];
        return build(vals, idx);
    }

    private TreeNode build(String[] vals, int[] idx) {
        String cur = vals[idx[0]++];
        if (cur.equals(NULL)) return null;
        TreeNode node = new TreeNode(Integer.parseInt(cur));
        node.left = build(vals, idx);
        node.right = build(vals, idx);
        return node;
    }
}

func serialize(root *TreeNode) string {
    vals := []string{}
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            vals = append(vals, "#")
            return
        }
        vals = append(vals, strconv.Itoa(node.Val))
        dfs(node.Left)
        dfs(node.Right)
    }
    dfs(root)
    return strings.Join(vals, ",")
}

func deserialize(data string) *TreeNode {
    vals := strings.Split(data, ",")
    idx := 0
    var build func() *TreeNode
    build = func() *TreeNode {
        if vals[idx] == "#" {
            idx++
            return nil
        }
        v, _ := strconv.Atoi(vals[idx])
        idx++
        node := &TreeNode{Val: v}
        node.Left = build()
        node.Right = build()
        return node
    }
    return build()
}

class Codec {
public:
    string serialize(TreeNode* root) {
        string out;
        ser(root, out);
        if (!out.empty()) out.pop_back();
        return out;
    }

    TreeNode* deserialize(string data) {
        vector<string> vals;
        string cur;
        for (char c : data) {
            if (c == ',') {
                vals.push_back(cur);
                cur.clear();
            } else {
                cur.push_back(c);
            }
        }
        vals.push_back(cur);
        int idx = 0;
        return de(vals, idx);
    }

private:
    void ser(TreeNode* node, string& out) {
        if (!node) { out += "#,"; return; }
        out += to_string(node->val) + ",";
        ser(node->left, out);
        ser(node->right, out);
    }

    TreeNode* de(vector<string>& vals, int& idx) {
        if (vals[idx] == "#") { idx++; return nullptr; }
        TreeNode* node = new TreeNode(stoi(vals[idx++]));
        node->left = de(vals, idx);
        node->right = de(vals, idx);
        return node;
    }
};

class Codec:
    def serialize(self, root):
        vals = []

        def dfs(node):
            if not node:
                vals.append('#')
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return ','.join(vals)

    def deserialize(self, data):
        vals = iter(data.split(','))

        def build():
            v = next(vals)
            if v == '#':
                return None
            node = TreeNode(int(v))
            node.left = build()
            node.right = build()
            return node

        return build()

var serialize = function(root) {
  const vals = [];
  const dfs = (node) => {
    if (!node) {
      vals.push('#');
      return;
    }
    vals.push(String(node.val));
    dfs(node.left);
    dfs(node.right);
  };
  dfs(root);
  return vals.join(',');
};

var deserialize = function(data) {
  const vals = data.split(',');
  let idx = 0;

  const build = () => {
    const v = vals[idx++];
    if (v === '#') return null;
    const node = new TreeNode(Number(v));
    node.left = build();
    node.right = build();
    return node;
  };

  return build();
};