二叉树¶

一句话：几乎所有二叉树题都能套进同一个框架——"整棵树的答案 = 用根节点的信息，组合左右子树各自的答案"。想清楚"子树需要返回什么信息给父节点"，代码基本就写出来了；唯一的例外是层序遍历，它天生是迭代（BFS）而非递归的活。

三种遍历：同一份模板，根的处理位置不同¶

void traverse(TreeNode root) {
    if (root == null) return;

    // ① 前序位置：刚进来，只知道"自己 + 从根传下来的参数"

    traverse(root.left);

    // ② 中序位置：左子树处理完了

    traverse(root.right);

    // ③ 后序位置：左右子树都处理完了
}

模板一样，位置不同 → 手里的信息不同 → 能解决的问题不同。 前序=我要往下传，中序=我要利用左边已完成，后序=我要往上汇报。

怎么直接写出三个序列：分块法¶

核心认知：三种遍历的分块结构完全相同（左块、右块、根），差别只在「根」放在块的哪个位置。

        A
       / \
      B   C
     / \   \
    D   E   F

第 1 步·切块：任何遍历都是三块拼出来的——左块（B 系）、右块（C 系）、根 A。

第 2 步·按根的位置拼：

第 3 步·递归套用：左块 = B 子树的遍历结果，右块 = C 子树的遍历结果，同样是"根在什么位置"的规则。B 子树（根 B、左 D、右 E）：前序 B D E、中序 D B E、后序 D E B。

三个自检规则¶

1. 前序的第一个 = 整棵树的根；后序的最后一个 = 整棵树的根
2. 每棵子树的根，是它那一段的第一个（前序）或最后一个（后序）——后序里 D E B 的 B 在末、F C 的 C 在末
3. 只有右孩子时，前序与中序相同（都是 根, 右），但后序是 右, 根
4. 上面 C 只有右孩子 F：前序 C F、中序 C F、后序 F C
5. 这是最容易写错的地方：把后序的 F C 误写成 C F

BST：中序即升序¶

定义（Binary Search Tree / 二叉搜索树）：对任意节点，左子树所有节点值 < 它 < 右子树所有节点值。 注意是整棵子树，不是只比直接孩子。

唯一必须记住的性质：

98-验证二叉搜索树 靠"中序必须递增"判定；230-BST中第K小的元素 中序数到第 k 个；538-把二叉搜索树转换为累加树 用反中序——降序遍历时"所有更大节点之和"已经算好，sum += node.val; node.val = sum; 即可；235-BST的最近公共祖先 利用大小关系判断往左还是往右走，一次向下即可。

陷阱：只比较父子不够¶

        10
       /  \
      5    15
          /  \
         6    20

逐条看父子关系全部合法（5<10、15>10、6<15、20>15），但它不是 BST：6 < 10 却位于 10 的右子树中——右子树所有节点都必须 > 10。中序走一遍 5, 10, 6, 15, 20 不是升序，立刻暴露。

正确判定有两条路： 1. 中序递增：遍历时记住上一个访问的值 prev，要求 node.val > prev 2. 上下界传参：给每个节点传一个开区间 (low, high) 一路收窄，10 的右子树得到 (10, +∞)，其中 15 的左子树得到 (10, 15)，6 不在区间内 → 违规

递归框架：子树返回什么¶

104-二叉树的最大深度、543-二叉树的直径、124-二叉树中的最大路径和 表面难度差很大，套路完全一样：写一个递归函数，让它返回"以当前节点为根、只往下延伸时的最优值"，同时在函数内部用左右子树的返回值去更新一个"跨过当前节点"的全局答案。

• 543 里子树返回"从该节点往下的最长链长度"，全局答案更新为"左链长度 + 右链长度"（跨过当前节点的路径）。
• 124 是同一个模板换成"最大路径和"：子树返回时要和 0 取 max（负贡献不如不要），全局答案同样是"左 + 右 + 当前节点值"跨节点组合。

关键教训：子树"返回给父节点用于继续递归"的值，和"更新全局答案"的值，往往不是同一个东西——返回值必须是"能继续延伸的单侧最优"，全局答案才是"两侧拼接的整体最优"，把这两者混为一谈是这类题最常见的错误。

98-验证二叉搜索树、230-BST中第K小的元素 利用的是 BST 的中序遍历天然有序这一性质，本质也是"递归时带着信息（上下界，或者计数）往下传"的变体，属于同一个框架的不同参数。

105-从前序与中序遍历构造二叉树 反过来利用递归框架构造树：前序的第一个元素是根，在中序里定位它即可切出左右子树的范围，递归重建——这也是"用递归划分左右子树"的思想，只是方向从"消费树"变成"生产树"。

BFS：唯一的迭代主场¶

102-层序遍历、199-二叉树的右视图 必须用队列做 BFS，而不是递归——因为这两题都需要按层处理（每层做统计，或每层只取最后一个），递归天然按"深度优先"的顺序访问节点，拿不到"同一层"这个分组，所以只能老老实实用队列，每轮把当前队列的全部节点出队、把它们的子节点入队。

BFS/DFS 分型表：做过题的归位¶

判断依据是算法总览的决策卡：答案以子树为单位 → DFS；以层为单位或求最短 → BFS；同位配对 → 都行选短的。

一个容易误判的例子：617 合并看起来像"遍历"题，其实答案是"同位配对"——每个位置只需知道彼此，不需要同层兄弟信息，所以递归版 7 行是最优解；层序版（成对入队、掉队嫁接）能做但更长。

BFS 的层判空细节见各题解：如 111 的"叶子才停"（左右都空）、617 的"掉队嫁接"（一边空直接 return 另一边）。

序列化：树的线性表示¶

297-二叉树的序列化与反序列化 本质是"给递归框架配一个可逆的线性编码"：前序遍历序列化时把空节点也显式记录（用占位符），反序列化时按同样的顺序消费序列重建——空节点不省略是能够无歧义还原结构的关键，否则同一个前序序列可能对应多棵树。

919-完全二叉树插入器 利用的是完全二叉树"按层序编号后，子节点下标可以直接计算"的性质（下标 i 的子节点是 2i+1/2i+2），插入时用层序遍历（队列）找到第一个还有空位的节点，是 BFS 而非递归框架的应用。