---

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

Binary Tree Serialization (Preorder)

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

思路

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

只要空节点也被记录，结构就不会丢。

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;
    }
}

Related

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