算法与AI · 知识点深化 · 算法思想
二叉树进阶：层序、BST、最近公共祖先、路径和
二叉树第一轮学了遍历，第二轮要解决具体问题：层序遍历分层、BST 验证、最近公共祖先、路径和、平衡判断。这些题都是遍历 + 后序处理的变体。这一页把高频题型套路化。
① 怎么学（4 步走，约 70 分钟）
先建立直觉再抠细节，按这四步走最稳：
1看图建立直觉（10 分钟）
读②③：先在脑子里画出本课核心结构图。
2记完整体系（15 分钟）
读④：把对比表和公式看懂，不要急着背。
3跟例题走一遍（20 分钟）
精读⑤：看三个例题怎么用知识点解题。
4刷题纠错（剩余时间）
做⑦⑩，错题回⑥诊断。
本课小目标学完你要能：① 写层序分层；② 验证 BST；③ 求 LCA；④ 路径和。
② 一图看懂：二叉树进阶题型
读法：中心是本课主题，四条分支展开核心维度，下方是典型应用与高频易错点。
③ 本质直觉：二叉树题就是"定义好递归函数"
二叉树题的秘诀：想清楚这个递归函数是干什么的，别试图一步想全树。
层序：队列，每层记录 size 一次性处理。
BST：中序遍历是升序，验证它就行。
LCA：函数定义：返回以 root 为根的树里 p/q 的最近公共祖先。左找、右找，都找到就是 root。
递归思维遇到树题先问：函数 f(root) 返回什么？假设左子树已经算好，怎么和 root/右组合？
④ 完整知识体系
高频题型套路
| 题型 | 套路 | 时间 |
|---|
| 层序分层 | 队列+每层 size | O(n) |
| BST 验证 | 中序遍历看升序 | O(n) |
| LCA | 后序左右找 | O(n) |
| 路径和 | DFS 累计减 | O(n) |
| 平衡判断 | 后序算高度差 | O(n) |
LCAif(!root||root==p||root==q) return root; l=dfs(left); r=dfs(right); return l&&r?root:l||r
层序while(q){ size=q.size(); 循环 size 次出队 }
BST 验证为什么要传上下界
只比较 root 和左右孩子不够，要保证左子树所有节点 < root < 右子树所有节点。传 min/max 递归。
⑤ 应用场景与例题
例1 LCA 题
root=3, p=5, q=1
在 3 的左右子树分别找到 5 和 1，说明 3 是 LCA。
例2 验证 BST
[5,1,4,null,null,3,6]
根 5，右孩子 4 比 5 小，不是 BST。
例3 路径和
root 到叶子和等于 targetSum
DFS 每步 target-=root.val，到叶子看 target==0。
做题心法先定义函数返回值，再递归左右，最后组装。
⑥ 高频错误诊断（4 条）
错误1：BST 只比较孩子要传上下界，保证整棵子树。
错误2：层序没分层每层记录 size。
错误3：LCA 思路混乱函数返回找到的节点，都找到就是 root。
错误4：路径和没判断叶子到叶子节点才判断和。
⑦ 考点真题演练（5 题）
考点分布
| 考法 | 出题形式 | 应对 |
|---|
| 层序 | 问怎么分层 | 每层 size |
| BST | 问验证方法 | 中序升序/上下界 |
| LCA | 问思路 | 后序左右找 |
| 平衡 | 问怎么判断 | 后序算高度 |
真题basic1. 层序遍历分层用什么数据结构？
真题mid2. 验证 BST 为什么要传上下界？
真题mid3. LCA 算法中，如果左右都找到节点，说明？
真题hard4. 平衡二叉树判断？
真题hard5. 路径和问题什么时候判断 target？
⑧ 必背知识点卡
层序：队列+每层 size
BST：中序升序，验证传上下界
LCA：左右都找到返回 root
路径和：DFS 累计，叶子判断
平衡：后序算高度差<=1
递归：先定义函数语义
时间：每个节点访问一次 O(n)
⑨ 动手输出：写 LCA
场景：求二叉树两节点最近公共祖先。
① 边界：root 空或等于 p/q，返回 root。
② 递归：左子树找，右子树找。
③ 判断：左右都不为空，root 是 LCA。
④ 否则：返回非空的那个。
⑤ 时间：O(n)。
口述思路函数返回找到的节点，都找到就是 root。
⑩ 分层练习（基础 + 中档 + 拔高）
▍基础 6 题
▍中档 5 题
中档1为什么 BST 只比较孩子不够？
可能孙子越界，要上下界。
中档2LCA 递归函数语义？
返回 root 树里 p/q 的 LCA。
中档3层序每层 size 作用？
知道这层出队几个。
▍拔高 5 题
拔高1路径 II 求所有路径？
DFS 记录 path，到叶子收集。
拔高2二叉树最大路径和？
后序，经过 root 的最大贡献。
拔高3序列化/反序列化？
前序遍历带 null。
拔高5完全二叉树节点数？
利用左右高度，满树直接算。
⑪ 记忆口诀 + 7 天复习计划
三句口诀① 层序队列 size 分层，BST 中序看升序。② LCA 后序左右找，路径和 DFS 到叶子。③ 递归先想函数语义，每个节点 O(n)。
| 天 | 任务 | 自检 |
|---|
| 第 1 天 | 读②③，写层序分层 | 代码对 |
| 第 2 天 | 背题型表 + 基础 6 题 | 套路记住 |
| 第 3 天 | 做中档 5 题，写 LCA | 逻辑对 |
| 第 4 天 | 做拔高 5 题，写路径和 | 边界对 |
| 第 5 天 | 做⑦真题 5 题 | 限时每题 5 分钟 |
| 第 6-7 天 | 合书白板写 LCA | 不看资料 |
← 返回算法与AI总览