Theory · Data Structure · Binary Tree
递归的艺术：四序遍历 · 迭代与 Morris · BST · 构造与序列化 —— LeetCode 树题家族的总纲
前中后层四序 + 递归/迭代/Morris 三写法，覆盖 80% 树题的骨架
整棵树 = 根 + 左右子树；想清楚"函数返回什么"就解了 80%
左小右大 → 中序即有序；插入/删除/验证全靠这条不变式
Why It Matters
文件夹里套文件夹、评论下面挂回复、网页的标签嵌标签、算式 (1+2)×3 的运算顺序——这些都是"一个东西下面挂着几个东西"。用数组或链表只能勉强编码，不能自然表达。
有序数组能二分（100 万条只要约 20 次比较），但插一条要挪一半元素；链表插一条很便宜，但查找只能从头走。两个都想要，就必须换结构。
在 1..7 里二分查 6：先看中间的 4（小了，往右），再看 6 的那一段的中间 6（找到了）。把每次"看的那个数"当作一个节点、"往左/往右"当作两条分叉画出来——你画出的正是一棵树，而且它满足"左边都比我小、右边都比我大"。这就是二叉搜索树 BST。
它能自然表达层级关系，又把"二分的每一步"固化成了节点：查找沿着分叉走 O(树高)，插入只改几个指针，不用挪动任何其他数据。代价是要小心树的形状——一旦长歪成一条链，O(log n) 就退回 O(n)。
| 需求 | 有序数组 | 链表 | 二叉搜索树 |
|---|---|---|---|
| 按值查找 | 快 O(log n) | 慢 O(n) | 快 O(树高) |
| 插入 / 删除 | 慢 O(n) 挪数据 | 快 O(1) | 快 O(树高) |
| 表达层级嵌套 | 不行 | 不行 | 天然 |
| 按顺序输出全部 | 天然有序 | 要排序 | 中序遍历即有序 |
Prerequisites & Glossary
| 术语 | 一句话理解（下一页配图逐个标出） |
|---|---|
| 节点 node / 边 edge | 装一个值的小方块；边就是"谁是谁的孩子"的连线 |
| 根 root / 叶 leaf | 最上面没有父亲的那个是根；下面没有孩子的是叶 |
| 子树 subtree | 任取一个节点连同它所有后代——本身又是一棵完整的树 |
| 深度 depth | 某节点到根有几条边（根的深度 0）——从上往下数 |
| 高度 height | 最深的叶子的深度——从下往上数；高度决定操作要走几步 |
| 度 degree | 一个节点有几个孩子；二叉树里只能是 0、1、2 |
| 完全二叉树 | 除最后一层外每层填满，最后一层靠左连续——能直接塞进数组 |
| 遍历 traversal | 把每个节点不重不漏访问一次的过程 |
| 前 / 中 / 后序 | 指的都是"什么时候处理根"：先处理根 / 夹在左右之间 / 最后处理 |
| BST 二叉搜索树 | 每个节点都满足"左子树都比我小、右子树都比我大"的树 |
数组与链表 → 节点+指针的写法、以及"为什么挪数据很贵"
复杂度分析 → O(log n) 的直觉：每一步砍掉一半
树的定义本身是递归的：一棵树 = 一个根 + 左子树 + 右子树（都可以为空）。
所以处理树的所有代码都是同一个动作：假设左右子树的答案已经算好了，我只负责用它们拼出自己的答案——空树是递归的终点。
在"处理左、处理右"这两步之间，把"处理根"插在哪里，就得到前序（根最先）、中序（在中间）、后序（根最后）；换成按层横着走就是层序。把"根什么时候被处理"想清楚，遍历就不用背了。
Terminology · Shapes
上一页的词在这张图里逐个标出；右侧三种形态请重点看最后一种——退化成链就是开场说的"O(log n) 变 O(n)"。
Properties · With Proofs
归纳：第 1 层 1 = 2⁰；每层节点最多翻倍。n 个节点、度数为 2 的树高度下界 ⌈log₂(n+1)⌉——这是"树操作 O(log n)"的来源。
边数守恒：树边数 = 节点数 − 1；每条边从父出发 → n₁ + 2n₂ = n₀ + n₁ + n₂ − 1 → n₀ = n₂ + 1。面试常让你现场推。
完全树前 h 层满有 2^h − 1 ≥ n → h ≤ log₂(n+1)；且 2^h ≤ n（第 h+1 层至少 1 个）→ h = ⌊log₂n⌋。堆的操作复杂度全靠它。
| 事实 | 数值 / 公式 |
|---|---|
| n 节点二叉树边数 | n − 1 |
| 满二叉树 k 层节点总数 | 2^k − 1 |
| n 节点完全树叶子数 | ⌈n/2⌉（数组存储时下标 ≥ n/2） |
| Catalan 数：n 节点二叉树形态数 | C(2n,n)/(n+1)——不同形态指数多 |
Four Traversals · Recursive
// DFS 三序：只差"处理自己"的位置 func dfs(root *TreeNode) { if root == nil { return } // 前序位置：进入节点时（根左右） dfs(root.Left) // 中序位置：左子树处理完（左根右） dfs(root.Right) // 后序位置：两棵子树都完（左右根） }
// BFS 层序：队列逐层推进 func levelOrder(root *TreeNode) [][]int { if root == nil { return nil } q := []*TreeNode{root}; res := [][]int{} for len(q) > 0 { n := len(q); layer := []int{} for i := 0; i < n; i++ { cur := q[0]; q = q[1:] layer = append(layer, cur.Val) if cur.Left != nil { q = append(q, cur.Left) } if cur.Right != nil { q = append(q, cur.Right) } } res = append(res, layer) } return res }
适合"进入节点时做事"：序列化、复制树、路径收集、前缀树构建。
BST 中序 = 升序序列——验证 BST、第 k 小（LC 230）、找中位数全靠它。
适合"需要孩子答案"：高度、直径、LCA、删除释放——后序是分治的位置。
最小深度、右侧视图（199）、每层最大值、之字打印——凡"按层"皆 BFS。
Same Tree · Three Orders
Iterative · Morris O(1) Space
递归的本质是系统栈，迭代版=自己管理：前序最好写（根入栈→弹→右先左后压）；中序"一路向左压栈、弹出访问、转右"；后序用"前序变形（根右左）再反转"最简洁。
栈里放 (节点, 是否已访问)：白色未访问——弹出时按倒序压孩子并标灰自己；灰色直接输出。一套代码出三序，免背三个模板。
利用"叶子的空指针"：找当前节点的中序前驱（左子树最右），在其右指针上挂回当前节点的线索。有线索→走左边；已有线索→访问自己、拆除线索、转右。时间 O(n)（每边最多走两次），空间 O(1)。
日常写递归（清晰）；深树防爆栈用显式栈；内存敏感/面试深挖才上 Morris——代价是临时破坏树结构，并发下不安全。
// 中序迭代：一路向左 + 栈回溯 func inorder(root *TreeNode) []int { stack, res := []*TreeNode{}, []int{} cur := root for cur != nil || len(stack) > 0 { for cur != nil { // 左链全压栈 stack = append(stack, cur) cur = cur.Left } cur = stack[len(stack)-1] // 弹出=访问 stack = stack[:len(stack)-1] res = append(res, cur.Val) cur = cur.Right // 转右 } return res }
Level Order · Queue
进入每轮循环前 n = len(q)，恰好弹 n 个——它们就是一整层。没有这个"快照"，队里新旧元素混在一起就分不了层。
分层基础上加奇偶标志：偶数层正序、奇数层把本层结果反转（或用 deque 两端出入）。只动"收集方向"，不动遍历顺序。
每层最后一个元素入选——分层后取 layer[n−1]。左侧视图/每层最大值（515）同款换判定位置。
最小深度 = 到最近叶子，不是到最近空孩子：某节点只有左孩子时，深度必须算到左子树的叶子。BFS 第一个遇到的叶子即答案（比 DFS 全扫快）。
| 题目 | 变形要点 |
|---|---|
| 102 层序遍历 M | 分层快照 n = len(q) |
| 103 锯齿形 M | 奇偶层收集方向反转 |
| 199 右侧视图 M | 每层末尾元素 |
| 515 每层最大值 M | 层内聚合 max |
| 111 最小深度 E | 首个叶子即停（叶子=无孩子） |
| 116 填充右侧指针 M | 层内串链：cur.Next 指向队头 |
Recursion Framework
把"对整棵树求 X"翻译成"根做一点事 + 左子树求 X + 右子树求 X"。想不出递归时，先画三层找规律。
这是最重要的决定：返回高度（104/110）、返回节点（236 LCA）、返回"是否"（101/98）、返回新根（226 翻转）。返回值定了，递归体就定了。
父→子用参数（路径、上下界），子→父用返回值，全局最优用外部变量（直径 543、最大路径和 124——返回值给父用、同时更新全局答案）。
// 直径 (LC 543)：三问示范 // Q2: 返回高度给父用 // Q3: 全局变量记最优（左深+右深） var ans int func diameterOfBinaryTree(root *TreeNode) int { ans = 0 depth(root) return ans } func depth(n *TreeNode) int { if n == nil { return 0 } l, r := depth(n.Left), depth(n.Right) if l+r > ans { // 过根的路径 ans = l + r } if l > r { return l + 1 } return r + 1 // 只能选一边向上 }
LeetCode Family Tree
| 家族 | 题目（编号 · 难度） | 核心套路 |
|---|---|---|
| 深度/平衡 | 104 最大深度 E · 110 平衡二叉树 E · 111 最小深度 E | 后序汇总高度；平衡 = 左右高差 ≤1 全树成立 |
| 结构变换 | 226 翻转 E · 617 合并两棵树 E · 114 展开为链表 M | 返回新根，子问题拼装 |
| 对称/相同 | 100 相同的树 E · 101 对称二叉树 E | 双参递归：左右镜像同步走 |
| 路径类 | 112 路径总和 E · 257 所有路径 E · 543 直径 E · 124 最大路径和 H | 参数传路径状态 / 全局变量记最优 |
| 祖先类 | 236 最近公共祖先 M · 235 BST 版 M | 后序返回命中；BST 版走分支 |
| BST 操作 | 98 验证 M · 230 第 k 小 M · 701 插入 M · 450 删除 M · 108 有序数组建树 E | 中序有序 + 上下界 |
| 构造/序列化 | 105 前中建树 M · 106 中后建树 M · 297 序列化 H | 定根 + 切分中序（下一页） |
Lowest Common Ancestor · LC 236
Build & Serialize · LC 105/106/297
前序首元素（或后序末元素）= 根；中序里根的左边全在左子树、右边全在右子树 → 递归切分。LC 105（前+中）、106（中+后）同构。
前+后序都知道根在哪，但分不开左右：单孩子时无法判断它在左边还是右边——前+后序不能唯一建树（每个内部节点度数都为 2 的"真二叉树"除外）。
用哈希表存"中序值→下标"避免每次线性查找；区间用闭区间 [inL, inR] 与前序偏移量 preIdx 递增——preIdx 是跨递归的全局游标（root 先建，先左后右的顺序不能反）。
前序 + null 占位符可以唯一反序列化（null 补齐了结构信息）；层序 + null 同理。反序列化用同一个"游标"逐个消费。LeetCode 官方输入格式就是层序+null。
| 序列组合 | 能唯一建树? | 原因 |
|---|---|---|
| 前序 + 中序 | ✓ | 根定位 + 左右切分 |
| 后序 + 中序 | ✓ | 同上（根在末尾） |
| 层序 + 中序 | ✓ | 层序逐层给根 |
| 前序 + 后序 | ✗（真二叉树除外） | 单孩子无法定边 |
Binary Search Tree
推论一：中序遍历 = 升序序列（验证/第 k 小/范围查询的地基）；推论二：查找/插入都沿单一路径，O(h)；推论三：退化成链时 h=n → 平衡树接管。
与当前节点比较，小往左大往右——像二分但走的是树。插入总是落在空位上（新节点永远是叶子）。
① 叶子：直接删；② 单孩子：子树上提顶替；③ 双孩子：用中序后继（右子树最左节点，或等价地中序前驱）的值覆盖根，再删掉那个后继——后继最多一个右孩子，回到情况①②。
后继 = 右子树最左；无右子树时 = 第一个"从左侧拐下来"的祖先。这就是 Morris 遍历找线索用的同一个指针游戏。
| 操作 | 平均 | 最坏（退化） |
|---|---|---|
| 查找 | O(log n) | O(n) |
| 插入 | O(log n) | O(n) |
| 删除 | O(log n) | O(n) |
| 中序遍历 | O(n) | O(n) |
| max/min | O(log n) | O(n) |
Validate BST · LC 98
left.Val < root.Val < right.Val 只保证局部有序——反例：5 → (1, 6 → (4, 7))，4 在 6 的左子树却大于根 5。BST 要求的是整棵子树的范围约束。
递归带 (min, max) 边界：进左子树把上界收紧为当前值，进右子树下界收紧为当前值；用 nil 表示无界（避免 int32/int64 边界值陷阱）。
BST ⇔ 中序序列严格递增。维护 prev 前驱指针，中序遍历中逐一比较——不用数值边界，天然免疫边界值问题。
① 节点值 = int 边界（LC 故意用 −2³¹）：比较用 nil 界或前驱指针；② "严格递增"不是"非递减"——相等即非法；③ 只查直接孩子是高频错误写法，主动说出来就是加分。
// 上下界法：nil = 无界，免疫边界值 func isValidBST(root *TreeNode) bool { return check(root, nil, nil) } func check(n, lo, hi *TreeNode) bool { if n == nil { return true } if lo != nil && n.Val <= lo.Val { return false } if hi != nil && n.Val >= hi.Val { return false } return check(n.Left, lo, n) && check(n.Right, n, hi) }
Complete Tree As Array
Cheat Sheet
| 遍历 | 根的处理时机 | 什么时候用它 |
|---|---|---|
| 前序 | 根 → 左 → 右 | 自顶向下传信息：复制树、打印路径、序列化 |
| 中序 | 左 → 根 → 右 | BST 专用：输出即升序、验证 BST、找第 k 小 |
| 后序 | 左 → 右 → 根 | 自底向上汇总：求高度/直径、删除释放、平衡判定 |
| 层序 | 按层横着走（队列） | 逐层输出、之字形、右视图、最小深度 |
| 第一问 | 整棵树的答案怎么由左右子树的答案拼出来？ |
| 第二问 | 递归函数返回什么（高度？是否合法？子树最大和？） |
| 第三问 | 跨子树的信息怎么传：参数往下传（上下界、路径），返回值往上带（汇总） |
| 终止条件 | 几乎总是 if root == nil；先写它再写别的 |
| 不变式 | 每个节点：左子树全部 < 它 < 右子树全部（不是只比父子） |
| 中序即有序 | 中序遍历输出严格递增——验证 BST 与找第 k 小都靠它 |
| 删除三情况 | 叶子直接删；一个孩子用孩子顶上；两个孩子用右子树最小（或左子树最大）替换后递归删那个 |
| 验证陷阱 | 只比较父子是错的；用上下界传递，边界用开区间，注意 int 极值与重复值 |
| 遍历 | 时间 O(n)；空间 O(树高)（递归栈），最坏 O(n)，Morris 可做到 O(1) |
| BST 查/插/删 | O(树高)：平衡时 O(log n)，退化成链时 O(n) |
| 完全二叉树数组化 | 下标从 0 起：左孩子 2i+1、右孩子 2i+2、父 (i−1)/2 |
| 两条性质 | 第 i 层最多 2i−1 个；叶子数 n₀ = 度 2 节点数 n₂ + 1 |
Interview QA · Part 1
先盖住答案自己答一遍，再展开对照——想不起来比看得顺眼记得牢；答不出的翻回上一页速查表。
树 = 根 + 两棵更小的树，子问题与原问题同构——递归是这种自相似的直译。调用栈深度 = 树高，退化树 O(n) 有爆栈风险（Go 无 TCO）。
机械翻译：栈存节点与访问状态。前序最好写；后序可"根右左前序 + 反转"取巧；颜色标记法（白=待访问、灰=已访问）一套代码出三序，不用背三个模板。
用叶子的空右指针存"回当前节点"的线索（中序前驱指向后继）：有线索→进左子树，访问完拆除线索恢复原树。时间 O(n)（每条边至多走两次），代价是遍历期间临时改结构、并发不安全。
每轮循环前记录 n=len(q)，本轮恰好弹 n 个——正好是一层。之后所有变形（之字 103、右视图 199、每层最大 515）都只改收集策略。
树边数 = 节点数 −1；从出边看 n₁+2n₂ = n₀+n₁+n₂−1 → n₀ = n₂+1。面试要求现场推，30 秒版：每加一个度 2 节点净多 1 个叶子。
层序落盘不留空洞，parent(i)=(i−1)/2、left=2i+1、right=2i+2 全部成立——零指针开销、缓存友好。这就是堆的实现方式（堆 deck）。
最小深度到最近叶子。节点只有单侧孩子时，min(左深,右深) 会错把"空孩子当叶子"——必须特判单孩子（或用 BFS 首个叶子即停）。
① 整树与子树关系；② 函数返回什么（高度/节点/bool/新根）；③ 跨子树信息走参数（向下）、返回值（向上）、全局变量（旁路）。三问答完代码就剩翻译。
Interview QA · Part 2
同样先自答再对照。这一页的题要"结论 + 一句推导/边界"才完整——只答结论会被继续追问。
前序/后序能定根，中序能分左右——两者缺一不可。前+后序在单孩子节点上二义（孩子在左还是右无法判断），不能唯一建树（真二叉树除外）。
只比父子（5→(1,6→(4,7)) 反例）；用 int 边界当初始界（−2³¹ 是合法值）。正确：nil 哨兵上下界传递，或中序 prev 前驱严格递增。
叶子直删；单孩子上提；双孩子用中序后继（右子树最左）换值再删后继——后继最多带一个右孩子，删除必落入前两种简单情况。对称地也可用前驱。
一般二叉树：后序返回命中节点，左右都非空即 LCA，O(n)。BST 版利用有序：pq 都小于根往左、都大于往右、首次分叉即 LCA——O(h) 无需遍历全树。
路径可"跨根"但递归只能返回"单边"——返回值给父用（高度），同时用全局变量更新"左+右"的跨根答案。两个题共用这个"返回值/答案分离"模式。
前序 + null 占位符：null 补齐"缺失的结构位"，反序列化按同一游标消费即可唯一重建；层序+null 同理。不带 null 的裸前序无法区分结构（同一前序可对应多棵树）。
需要孩子结果的（高度、直径、LCA、删除）→ 后序；需要祖先状态的（路径总和、构建BST、上下界）→ 前序带参数下行。中序几乎只在 BST 里用（有序性）。
Related & References
参考来源（本 deck 结论可溯源至下列一手材料）
| CLRS ch12 · Binary Search Trees | BST 性质、插入删除（含后继替换）形式化 |
| LeetCode 102/103/199/105/106/297/98/450/236/543 题解 | 遍历变形、构造、验证、LCA 与路径套路 |
| J. H. Morris · Traversing Binary Trees Simply and Cheaply (1979) | Morris 线索化遍历原始论文 |
| oi-wiki.org/ds/binary-tree | 性质推导与遍历模板（中文对照） |
| 完全二叉树数组化父子公式 | 堆实现标准结论（CLRS ch6 / 本仓库堆 deck 互勘） |