[!info] related notes 算法面试题型 MOC 二叉树高频题

Binary Tree Serialization (Level-Order)

LeetCode: https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

思路

• BFS 输出节点值。
• 遇到空孩子也输出占位符（例如 #），否则结构会丢。
• 反序列化时用队列逐层挂孩子。

本示例的格式

空树输出 #；非空树按层记录真实节点和空孩子，每个 token 后有逗号，空节点本身不再展开。只有根 1 时输出 1,#,#,；根 1 的左孩子为 2、右孩子为空时输出 1,2,#,#,#,。某些小树与先序编码恰好一致，不表示两套格式可互换。

这里保留全部空孩子 token，没有采用“去掉尾部 #”的压缩约定。节点值允许重复；对象身份、共享引用与环不属于本树格式。

Java Template

import java.util.*;

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

    public String serialize(TreeNode root) {
        if (root == null) return NIL;
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            if (cur == null) {
                sb.append(NIL).append(SEP);
                continue;
            }
            sb.append(cur.val).append(SEP);
            q.add(cur.left);
            q.add(cur.right);
        }
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if (data == null || data.isEmpty() || data.equals(NIL)) return null;
        String[] parts = data.split(SEP);
        int idx = 0;

        TreeNode root = node(parts[idx++]);
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);

        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            if (cur == null) continue;
            if (idx < parts.length) {
                cur.left = node(parts[idx++]);
                q.add(cur.left);
            }
            if (idx < parts.length) {
                cur.right = node(parts[idx++]);
                q.add(cur.right);
            }
        }
        return root;
    }

    private TreeNode node(String s) {
        if (s.equals(NIL) || s.isEmpty()) return null;
        return new TreeNode(Integer.parseInt(s));
    }
}

实现约束

TreeNode 由题目提供。序列化器会把 null 放入队列，所以这里使用允许 null 的 LinkedList；不能直接替换成拒绝 null 的 ArrayDeque。

解码器对 null、空字符串和 # 返回空树，也容忍尾部缺失的孩子和部分多余 token；这是示例的宽松行为，不是已经验证格式合法。面对外部数据，应定义精确语法并检查每个 token、消费数量和输入大小。

按固定范围整数计，时间和输出 O(n)。BFS 队列 O(w)，反序列化保存的 parts 数组 O(n)；w 为最大层节点数。

Related

• 二叉树先序序列化
• 二叉树高频题