题目描述
思路解析
一句话答案：LeetCode 297 二叉树的序列化与反序列化的经典解法是先序 DFS 加占位符：序列化按根、左、右的顺序把节点值写成字符串，空孩子写 # 占位；反序列化把字符串切成 token 队列，按完全相同的先序顺序逐个取出重建。两个方向各处理每个 token 一次，时间 O(n)、空间 O(n)。
这道题真正要设计的是什么
题目要求写一对互逆的函数：serialize 把任意二叉树编码成一个字符串，deserialize 再把这个字符串还原成一模一样的树，deserialize(serialize(root)) 必须等于原树。难点不在遍历本身，而在于字符串必须携带足够的信息——不但要记录每个节点的值，还要能还原树的形状。同样一串值 1,2,3，既可能是一条斜向一边的链，也可能是一棵根带两个孩子的树，只记值是不够的。
为什么必须给空孩子写 # 占位符
形状信息丢失的根源在于：普通遍历序列把空位置跳过了，读串的人分不清「下一个值是当前节点的孩子，还是拐回上层挂在别处」。补救办法是把空也当成一个字符写出来：先序遍历时每碰到一个空孩子就写一个 #。这样每个节点名下左、右两个孩子位置都有明确交代，值序列和树的形状就一一对应了。
代价是串变长：n 个节点会带出 n+1 个 #（共 2n 个孩子位置，其中 n-1 个被真实节点占据）。多出的这点长度换来的是零歧义，这是序列化方案里常见的交易。
为什么选先序遍历而不是中序或层序
先序的好处是根永远排在串的最前面：反序列化取出第一个 token 就能立刻建出根；按「根、左、右」的定义，紧随其后的一段恰好是完整的左子树，再往后是完整的右子树，天然适合递归重建。中序把根夹在左右子树中间，拿到串时不知道该从哪里切开，难以定位根。层序配合占位符同样可行（用队列逐层重建），但先序递归的代码最短，还和序列化共用同一套遍历骨架。真正的铁律只有一条：序列化和反序列化必须用同一种顺序，顺序一旦错位，孩子就会挂错位置、整棵树扭曲。
反序列化为什么取一个 token 就能精确归位
把字符串按逗号切成 token 队列后，重建函数的逻辑是：从队头取一个 token，是 # 就返回空，否则建节点、先递归建左子树、再递归建右子树。正确性来自先序串的结构不变量：任何一棵子树在串里都是连续的一段，且这段的开头就是该子树的根。递归建左子树时会恰好消费掉左子树对应的那段 token，返回时队头自动停在右子树的开头——不需要任何额外的分隔符或长度标记。
一个隐蔽的坑：# 也必须从队列里消费掉。它虽然不建节点，但占着一个位置，不弹出的话后续 token 全部错位，还原出来的树会整体歪掉。
复杂度是多少，哪里容易翻车
序列化和反序列化都是每个 token 恰好处理一次，时间各为 O(n)。空间 O(n)：字符串本身是线性长度，递归栈深等于树高 h，最坏退化成链时也是 O(n)。
两个高频错误：一是不写空占位符，看似省了空间，实则丢了形状信息，根本还原不出唯一的树；二是两边遍历顺序不一致，比如序列化用先序、反序列化却按别的顺序读，token 数量对得上但结构全错。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
一句话抓住本质：序列化用先序（根→左→右）把值和 # 占位写成一串；反序列化把这串切成 token 队列，按完全相同的先序顺序一个个取出来重建。顺序一致是可逆的关键。下面两阶段逐帧看。
准备 · 序列化整棵树：先看清这棵树，根是 1，一共 9 个节点。序列化就是把这棵树压成一行字符串：我们用先序遍历（根→左→右），每碰到一个节点就把它的值记下来；碰到空位置就记一个 # 占位，这样结构才不会丢。
访问 1 → 写入串：先序遍历踩到节点 1（根）。根先写：把它的值 1 追加到字符串末尾，标蓝表示已写出。接着按「先左后右」继续往下走。
访问 2 → 写入串：先序遍历踩到节点 2（1 的左孩子）。根先写：把它的值 2 追加到字符串末尾，标蓝表示已写出。接着按「先左后右」继续往下走。
访问 4 → 写入串：先序遍历踩到节点 4（2 的左孩子）。根先写：把它的值 4 追加到字符串末尾，标蓝表示已写出。接着按「先左后右」继续往下走。
访问 8 → 写入串：先序遍历踩到节点 8（4 的左孩子）。根先写：把它的值 8 追加到字符串末尾，标蓝表示已写出。接着按「先左后右」继续往下走。
空位 → 写 #（8 的左孩子）：走到「8 的左孩子」，这里是空的。先序序列化遇到空位置不能跳过——必须写一个 # 占位，否则反序列化时分不清「有没有这个孩子」。串末尾追加 #。
空位 → 写 #（8 的右孩子）：走到「8 的右孩子」，这里是空的。先序序列化遇到空位置不能跳过——必须写一个 # 占位，否则反序列化时分不清「有没有这个孩子」。串末尾追加 #。
访问 9 → 写入串：先序遍历踩到节点 9（4 的右孩子）。根先写：把它的值 9 追加到字符串末尾，标蓝表示已写出。接着按「先左后右」继续往下走。
空位 → 写 #（9 的左孩子）：走到「9 的左孩子」，这里是空的。先序序列化遇到空位置不能跳过——必须写一个 # 占位，否则反序列化时分不清「有没有这个孩子」。串末尾追加 #。
空位 → 写 #（9 的右孩子）：走到「9 的右孩子」，这里是空的。先序序列化遇到空位置不能跳过——必须写一个 # 占位，否则反序列化时分不清「有没有这个孩子」。串末尾追加 #。
访问 5 → 写入串：先序遍历踩到节点 5（2 的右孩子）。根先写：把它的值 5 追加到字符串末尾，标蓝表示已写出。接着按「先左后右」继续往下走。
空位 → 写 #（5 的左孩子）：走到「5 的左孩子」，这里是空的。先序序列化遇到空位置不能跳过——必须写一个 # 占位，否则反序列化时分不清「有没有这个孩子」。串末尾追加 #。
空位 → 写 #（5 的右孩子）：走到「5 的右孩子」，这里是空的。先序序列化遇到空位置不能跳过——必须写一个 # 占位，否则反序列化时分不清「有没有这个孩子」。串末尾追加 #。
访问 3 → 写入串：先序遍历踩到节点 3（1 的右孩子）。根先写：把它的值 3 追加到字符串末尾，标蓝表示已写出。接着按「先左后右」继续往下走。
访问 6 → 写入串：先序遍历踩到节点 6（3 的左孩子）。根先写：把它的值 6 追加到字符串末尾，标蓝表示已写出。接着按「先左后右」继续往下走。
空位 → 写 #（6 的左孩子）：走到「6 的左孩子」，这里是空的。先序序列化遇到空位置不能跳过——必须写一个 # 占位，否则反序列化时分不清「有没有这个孩子」。串末尾追加 #。
空位 → 写 #（6 的右孩子）：走到「6 的右孩子」，这里是空的。先序序列化遇到空位置不能跳过——必须写一个 # 占位，否则反序列化时分不清「有没有这个孩子」。串末尾追加 #。
访问 7 → 写入串：先序遍历踩到节点 7（3 的右孩子）。根先写：把它的值 7 追加到字符串末尾，标蓝表示已写出。接着按「先左后右」继续往下走。
空位 → 写 #（7 的左孩子）：走到「7 的左孩子」，这里是空的。先序序列化遇到空位置不能跳过——必须写一个 # 占位，否则反序列化时分不清「有没有这个孩子」。串末尾追加 #。
空位 → 写 #（7 的右孩子）：走到「7 的右孩子」，这里是空的。先序序列化遇到空位置不能跳过——必须写一个 # 占位，否则反序列化时分不清「有没有这个孩子」。串末尾追加 #。
序列化完成 · 整串就绪：整棵树走完了，先序序列化得到这一行字符串：1,2,4,8,#,#,9,#,#,5,#,#,3,6,#,#,7,#,#。9 个节点值 + 10 个 # 占位，共 19 个 token。结构信息全在里面、毫无歧义——下面把它反序列化，原样重建出这棵树。
准备 · 反序列化（空树起步）：反序列化从一棵空树开始。关键：用和序列化完全相同的先序顺序，把字符串切成 token 队列，从队头一个个取。取到值就建节点，取到 # 就是空、回头。顺序一致，重建出的树就和原树一模一样。
取到 1 → 建节点（根）：从队头取出 1，新建一个值为 1 的节点（根），它在树上浮现出来（绿）。接着先递归建它的左子树、再建右子树——和序列化时「根→左→右」的顺序严丝合缝。
取到 2 → 建节点（1 的左孩子）：从队头取出 2，新建一个值为 2 的节点（1 的左孩子），它在树上浮现出来（绿）。接着先递归建它的左子树、再建右子树——和序列化时「根→左→右」的顺序严丝合缝。
取到 4 → 建节点（2 的左孩子）：从队头取出 4，新建一个值为 4 的节点（2 的左孩子），它在树上浮现出来（绿）。接着先递归建它的左子树、再建右子树——和序列化时「根→左→右」的顺序严丝合缝。
取到 8 → 建节点（4 的左孩子）：从队头取出 8，新建一个值为 8 的节点（4 的左孩子），它在树上浮现出来（绿）。接着先递归建它的左子树、再建右子树——和序列化时「根→左→右」的顺序严丝合缝。
取到 # → 空（8 的左孩子）：从队头取出 #。# 代表「8 的左孩子」是空的——不建节点、直接返回，让上一层去处理它的下一个孩子。# 占位在这里发挥作用：精准告诉我们「此处无孩子」。
取到 # → 空（8 的右孩子）：从队头取出 #。# 代表「8 的右孩子」是空的——不建节点、直接返回，让上一层去处理它的下一个孩子。# 占位在这里发挥作用：精准告诉我们「此处无孩子」。
取到 9 → 建节点（4 的右孩子）：从队头取出 9，新建一个值为 9 的节点（4 的右孩子），它在树上浮现出来（绿）。接着先递归建它的左子树、再建右子树——和序列化时「根→左→右」的顺序严丝合缝。
取到 # → 空（9 的左孩子）：从队头取出 #。# 代表「9 的左孩子」是空的——不建节点、直接返回，让上一层去处理它的下一个孩子。# 占位在这里发挥作用：精准告诉我们「此处无孩子」。
取到 # → 空（9 的右孩子）：从队头取出 #。# 代表「9 的右孩子」是空的——不建节点、直接返回，让上一层去处理它的下一个孩子。# 占位在这里发挥作用：精准告诉我们「此处无孩子」。
取到 5 → 建节点（2 的右孩子）：从队头取出 5，新建一个值为 5 的节点（2 的右孩子），它在树上浮现出来（绿）。接着先递归建它的左子树、再建右子树——和序列化时「根→左→右」的顺序严丝合缝。
取到 # → 空（5 的左孩子）：从队头取出 #。# 代表「5 的左孩子」是空的——不建节点、直接返回，让上一层去处理它的下一个孩子。# 占位在这里发挥作用：精准告诉我们「此处无孩子」。
取到 # → 空（5 的右孩子）：从队头取出 #。# 代表「5 的右孩子」是空的——不建节点、直接返回，让上一层去处理它的下一个孩子。# 占位在这里发挥作用：精准告诉我们「此处无孩子」。
取到 3 → 建节点（1 的右孩子）：从队头取出 3，新建一个值为 3 的节点（1 的右孩子），它在树上浮现出来（绿）。接着先递归建它的左子树、再建右子树——和序列化时「根→左→右」的顺序严丝合缝。
取到 6 → 建节点（3 的左孩子）：从队头取出 6，新建一个值为 6 的节点（3 的左孩子），它在树上浮现出来（绿）。接着先递归建它的左子树、再建右子树——和序列化时「根→左→右」的顺序严丝合缝。
取到 # → 空（6 的左孩子）：从队头取出 #。# 代表「6 的左孩子」是空的——不建节点、直接返回，让上一层去处理它的下一个孩子。# 占位在这里发挥作用：精准告诉我们「此处无孩子」。
取到 # → 空（6 的右孩子）：从队头取出 #。# 代表「6 的右孩子」是空的——不建节点、直接返回，让上一层去处理它的下一个孩子。# 占位在这里发挥作用：精准告诉我们「此处无孩子」。
取到 7 → 建节点（3 的右孩子）：从队头取出 7，新建一个值为 7 的节点（3 的右孩子），它在树上浮现出来（绿）。接着先递归建它的左子树、再建右子树——和序列化时「根→左→右」的顺序严丝合缝。
取到 # → 空（7 的左孩子）：从队头取出 #。# 代表「7 的左孩子」是空的——不建节点、直接返回，让上一层去处理它的下一个孩子。# 占位在这里发挥作用：精准告诉我们「此处无孩子」。
取到 # → 空（7 的右孩子）：从队头取出 #。# 代表「7 的右孩子」是空的——不建节点、直接返回，让上一层去处理它的下一个孩子。# 占位在这里发挥作用：精准告诉我们「此处无孩子」。
参考代码
public class Codec { // 序列化：先序遍历，空节点写 "#"，逗号分隔 public String serialize(TreeNode root) { StringBuilder sb = new StringBuilder(); dfsSer(root, sb); return sb.toString(); } private void dfsSer(TreeNode node, StringBuilder sb) { if (node == null) { sb.append("#,"); return; } // 空 → # 占位 sb.append(node.val).append(","); // 根先写 dfsSer(node.left, sb); // 再左 dfsSer(node.right, sb); // 后右 } // 反序列化：按逗号切成队列，先序逐个重建 public TreeNode deserialize(String data) { Deque<String> q = new ArrayDeque<>(Arrays.asList(data.split(","))); return build(q); } private TreeNode build(Deque<String> q) { String t = q.poll(); // 取队头 if (t.equals("#")) return null; // # → 空 TreeNode node = new TreeNode(Integer.parseInt(t)); node.left = build(q); // 先建左 node.right = build(q); // 再建右 return node; }}复杂度
- 时间：O(n)，序列化/反序列化各访问每个 token 一次
- 空间：O(n)，字符串 O(n) + 递归栈 O(h)；最坏(链)O(n)
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最近公共祖先
LeetCode 236 · 中等 · 沿着 树 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题