BFS

#BFS
思路：队列

1. 先让根节点入队列，然后依次弹出
2. 出队列时，有左加左，有右加右

按层输出的 BFS

102.二叉树的层序遍历.cpp
思路 1：用一个 hashmap 记录每个节点的层数，每次队列加入节点时，将该节点也加入 hashmap，从而维护层数
思路 2：用 l, r 指针模拟队列，队列 size 即为一层的节点数，一次弹出 size 个节点并完成入队列操作

锯齿状 BFS

103.二叉树的锯齿形层序遍历.cpp
思路：跟按层输出一样，只是在收集 size 个节点时，收集方向不断交替

最大特殊宽度

思路：与 二叉树问题#按层输出的 BFS 相同，但是通过计算节点位置直接得到宽度（若某一节点位置为 $i$，其两个子节点分别为 $2*i$ 和 $2*i+1$）

按层先序列化与反序列化

DFS

最大深度与最小深度

思路：递归

先序遍历序列化和反序列化

树的中序遍历无法与树一一对应，因此无法反序列化，先（后）序可以

完全二叉树

判断完全二叉树

958.二叉树的完全性检验.cpp
思路 1：flag 标识 + 层序遍历

1. 如果有右无左，则不是
2. 如果一旦出现孩子不全，则后面必须全是叶节点（flag 标识）

另一种思路：将空节点入队列，一旦遇到空节点，则后面必须全为空节点

求完全二叉树节点个数

222.完全二叉树的节点个数.cpp
思路：递归，公式求满二叉树节点数，复杂度为 $O(\log n)$

1. 求左右子树最大深度 rh 和 lh（完全二叉树深度即为一直向左最大深度）
2. 如果左边高，右边为满二叉树，个数为 $1+2^{rh}-1=2^{rh}$
   1. 递归求右树节点个数
3. 如果左右一样高，左边为满二叉树，个数为 $1+2^{lh}-1=2^{lh}$
   1. 递归求左树节点个数

最近共同祖先（lca）

普通二叉树上 lca

思路：DFS，关键在于把什么传上去给父节点

1. 两个子节点都为空，返回空（叶子节点）
2. 两个子节点一个为空一个不空，返回不空的（可能为包含关系，则先遇到谁就直接返回；可能为并列但是还没遇到 lca，先把自己返回上去）
3. 两个子节点都不空，返回自己（并列关系，该节点为 lca，返回自己）

搜索二叉树（BST）上 lca

235.二叉搜索树的最近公共祖先.cpp

思路：利用 BST 的有序性，遇到某个节点 $x$ 时

1. 若 $p\leq x\leq q$，则 $x$ 为 lca
2. 若 $p,q<x$，则 lca 在 $x$ 左子树上
3. 若 $p,q>x$，则 lca 在 $x$ 右子树上

记录 lca 路径

思路：DFS+ 回溯恢复现场

验证平衡二叉树

思路：递归

验证搜索二叉树

思路 1：中序遍历单调上升
思路 2：