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

Binary Tree Serialization (Preorder)

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

思路

• 先序遍历输出节点值。
• 空节点输出占位符（例如 #）。
• 反序列化时按相同顺序读 token，递归构建。

节点值为整数时，先序顺序配合空节点标记可唯一恢复结构，即使节点值重复也可以；这不同于仅有前序/中序且依赖值唯一的构造算法。输入应是真正的树，不包含环或共享子节点，反序列化创建新节点，不保留原对象身份。

本示例的格式

• 遍历顺序是根、左、右，整数与 # 用逗号分隔，每个 token 后有逗号。
• 空树输出 #,；只有根 1 的树输出 1,#,#,。
• 根 1 的左孩子为 2、右孩子为空时，输出 1,2,#,#,#,。
• Java String.split 默认丢弃末尾空字符串，因此这里接受序列化器产生的末尾逗号。

此格式与 层序序列化不互通，不能根据“都用了逗号与 #”混用解码器。

Java Template

import java.util.*;

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

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

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

    public TreeNode deserialize(String data) {
        Deque<String> q = new ArrayDeque<>(Arrays.asList(data.split(SEP)));
        return de(q);
    }

    private TreeNode de(Deque<String> q) {
        if (q.isEmpty()) return null;
        String s = q.pollFirst();
        if (s.equals(NIL)) return null;
        TreeNode node = new TreeNode(Integer.parseInt(s));
        node.left = de(q);
        node.right = de(q);
        return node;
    }
}

适用边界

TreeNode 由题目环境提供。本解码器依赖输入来自配对的 serialize，并未严格校验格式：队列提前为空会补出 null，树构建完成后也未检查多余 token。它不是外部不可信数据的完整解析器；复用时需拒绝截断、余量、非法整数，并限制数据长度与递归深度。

对 n 个节点，序列化含 2n + 1 个值/空位 token；按固定范围整数计时间和输出为 O(n)。递归栈 O(h)，反序列化还用 O(n) token 队列。

Related

• 二叉树按层序列化
• 二叉树高频题