题目描述
思路解析动画文字版
记住「序列化 = 前序、不存 null;反序列化 = 前序 + (lo, hi) 区间唯一定位」,下面分两段逐帧套它。
序列化 · 开始：先做序列化。规则是前序遍历:每到一个节点,先把它的值写进序列,再去左子树、最后去右子树。注意整个过程不写任何 null,这是 BST 比普通二叉树省空间的地方。
序列化 · 输出 50：前序走到节点 50(紫色),把它的值写进序列,序列现在是 50。先记根,再去左子树。
序列化 · 输出 30：前序走到节点 30(紫色),把它的值写进序列,序列现在是 50,30。接着按根、左、右的顺序继续。
序列化 · 输出 20：前序走到节点 20(紫色),把它的值写进序列,序列现在是 50,30,20。接着按根、左、右的顺序继续。
序列化 · 输出 40：前序走到节点 40(紫色),把它的值写进序列,序列现在是 50,30,20,40。接着按根、左、右的顺序继续。
序列化 · 输出 80：前序走到节点 80(紫色),把它的值写进序列,序列现在是 50,30,20,40,80。接着按根、左、右的顺序继续。
序列化 · 输出 70：前序走到节点 70(紫色),把它的值写进序列,序列现在是 50,30,20,40,80,70。接着按根、左、右的顺序继续。
序列化 · 输出 90：前序走到节点 90(紫色),把它的值写进序列,序列现在是 50,30,20,40,80,70,90。这是最后一个节点。
序列化 · 完成：序列化完成,得到前序串 50,30,20,40,80,70,90,一共 7 个值、没有一个 null。接下来反过来,只凭这串数把整棵 BST 还原出来。
反序列化 · 开始：开始反序列化。手里只有前序串 50,30,20,40,80,70,90。我们从左往右取值,每个位置都带一个允许区间 (lo, hi):根节点的区间是 (-∞, +∞),最宽松。
反序列化 · 建 50：根:取到值 50,它满足 -∞ < 50 < +∞,于是在这里建节点 50。接着它的左子树区间收紧为 (-∞, 50)、右子树区间为 (50, +∞),继续往下递归。
反序列化 · 建 30：节点 50 的左孩子:取到值 30,它满足 -∞ < 30 < 50,于是在这里建节点 30。接着它的左子树区间收紧为 (-∞, 30)、右子树区间为 (30, 50),继续往下递归。
反序列化 · 建 20：节点 30 的左孩子:取到值 20,它满足 -∞ < 20 < 30,于是在这里建节点 20。接着它的左子树区间收紧为 (-∞, 20)、右子树区间为 (20, 30),继续往下递归。
反序列化 · 节点 20 的左孩子为空：轮到节点 20 的左孩子,它的允许区间是 (-∞, 20)。但下一个待读的值 40 不落在区间里,说明这里没有节点,直接判为空,既不取值也不前进,回到上一层。
反序列化 · 节点 20 的右孩子为空：轮到节点 20 的右孩子,它的允许区间是 (20, 30)。但下一个待读的值 40 不落在区间里,说明这里没有节点,直接判为空,既不取值也不前进,回到上一层。
反序列化 · 建 40：节点 30 的右孩子:取到值 40,它满足 30 < 40 < 50,于是在这里建节点 40。接着它的左子树区间收紧为 (30, 40)、右子树区间为 (40, 50),继续往下递归。
反序列化 · 建 80：节点 50 的右孩子:取到值 80,它满足 50 < 80 < +∞,于是在这里建节点 80。接着它的左子树区间收紧为 (50, 80)、右子树区间为 (80, +∞),继续往下递归。
反序列化 · 建 70：节点 80 的左孩子:取到值 70,它满足 50 < 70 < 80,于是在这里建节点 70。接着它的左子树区间收紧为 (50, 70)、右子树区间为 (70, 80),继续往下递归。
反序列化 · 建 90：节点 80 的右孩子:取到值 90,它满足 80 < 90 < +∞,于是在这里建节点 90。接着它的左子树区间收紧为 (80, 90)、右子树区间为 (90, +∞),继续往下递归。
反序列化 · 完成：整串读完,还原出的 BST 和原来完全一样。验证一下它的中序是 20,30,40,50,70,80,90,严格升序,确实是合法 BST。这正是 BST 的妙处:前序串配上 (lo,hi) 区间,每个值的位置都被唯一确定。
边界:空树空串、单节点单值、单边链靠区间照样唯一还原。
两个追问:对比 lc297 普通树要存 null;前序最契合区间还原。
参考代码
from typing import Optionalclass TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Codec: def serialize(self, root: Optional[TreeNode]) -> str: vals = [] def dfs(node): if node: vals.append(str(node.val)) dfs(node.left) dfs(node.right) dfs(root) return ','.join(vals) def deserialize(self, data: str) -> Optional[TreeNode]: if not data: return None vals = list(map(int, data.split(','))) i = 0 def build(lo, hi): nonlocal i if i == len(vals) or not (lo < vals[i] < hi): return None node = TreeNode(vals[i]) i += 1 node.left = build(lo, node.val) node.right = build(node.val, hi) return node return build(float('-inf'), float('inf'))复杂度
- 时间：O(n)，序列化每个节点访问一次;反序列化每个值取用一次、每次区间判断是常数,共 O(n)
- 空间：O(n)，输出序列本身 O(n);递归栈深度等于树高 h,最坏退化成链时 O(n)
易错点
面试追问把动画讲成自己的话
追问和普通二叉树的序列化(lc297)有什么区别?
追问能不能用层序而不是前序来序列化 BST 并省 null?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
在每个树行中找最大值
LeetCode 515 · 中等 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题