SYSTEM
今日二叉树算法全集笔记(统一模板 \+ 每道题拆解 \+ 规律总结)
src/content/notes/algorithm/二叉树.md 今日二叉树算法全集笔记(统一模板 + 每道题拆解 + 规律总结)
一、今天所有二叉树题的【统一底层规律】(最重要)
1. 二叉树递归万能公式(所有题 100% 通用)
递归固定三步:
① 终止条件:root == null 直接返回
② 递归左子树、递归右子树
③ 结合左右结果,处理当前节点
所有二叉树题目,全部都是这三步!
区别只在于:第三步你要做什么业务逻辑
-
求深度 → 左右取最大 +1
-
翻转树 → 交换左右
-
对称树 → 交叉对比
-
公共祖先 → 左右查找结果分类讨论
2. 二叉树递归只有两种顺序
前序:先处理自己,再递归左右(翻转、遍历)
后序:先递归左右,再处理自己(深度、LCA)
你今天写的所有题,逃不出这两种。
二、逐题精细总结(思路 + 代码细节 + 固定写法)
1. 二叉树中序遍历(LeetCode94)
核心思路
顺序:左 → 根 → 右
先递归左子树,再存当前值,最后递归右子树。
递归代码固定模板
// 共享集合存结果
List<Integer> res = new ArrayList<>();
dfs(root);
void dfs(TreeNode node){
if(node == null) return;
dfs(node.left);
res.add(node.val);
dfs(node.right);
}
固定模板(必考)
口诀:一路左压栈、弹出存值、切右树
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
res.add(cur.val);
cur = cur.right;
}
关键细节
-
外层循环必须 cur != null || !stack.isEmpty()
-
中序是 pop 时 add(前序是 push 时 add)
-
必须用 Deque+ArrayDeque 做栈,不用 Stack 类
2. 二叉树最大深度(LeetCode104)
核心思路
后序递归:先算左、先算右,再算自己
当前树深度 = max(左深度, 右深度) + 1
固定模板
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
代码细节
-
maxDepth(root.left) 求的是「整棵左子树」深度,不是单个节点
-
null 节点返回 0,是递归的兜底
-
+1 代表算上当前根节点
3. 翻转二叉树(LeetCode226)
核心思路
前序递归:先交换自己,再递归左右
每一个节点都要交换左右孩子,整棵树自然镜像翻转。
固定模板
public TreeNode invertTree(TreeNode root) {
if(root == null) return null;
// 交换自己的左右
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
// 递归处理子树
invertTree(root.left);
invertTree(root.right);
return root;
}
关键细节
-
交换完再递归,所以左右子树递归的是「已经交换后的新树」
-
不需要接收返回值,属于原地修改树
4. 对称二叉树(LeetCode101)
核心思路
对比 两棵子树是否镜像
镜像规则:
-
节点值相等
-
左的左 ⇋ 右的右
-
左的右 ⇋ 右的左
固定模板
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return check(root.left, root.right);
}
private boolean check(TreeNode a, TreeNode b){
if(a == null && b == null) return true;
if(a == null || b == null) return false;
return a.val == b.val
&& check(a.left, b.right)
&& check(a.right, b.left);
}
易错点(高频坑)
❌ 错误:check(a.left,b.left) 这是比较相同,不是镜像
✅ 正确:交叉对比
5. 二叉树最近公共祖先 LCA(LeetCode236)
核心思路
后序递归:左右先搜,搜到结果向上返回
返回值含义:找到 p / q / 祖先 / null
三种最终判断逻辑(背诵)
-
左有、右有 → 当前 root 就是 LCA
-
左空、右有 → 结果在右边
-
右空、左有 → 结果在左边
固定模板
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left != null && right != null) return root;
return left == null ? right : left;
}
核心细节
只要左右各搜到一个节点,当前节点一定是最近公共祖先
三、今日所有题目【终极通用规律】
1. 二叉树递归万能结构(100%通用)
function(TreeNode root){
// 1. 终止条件
if(root == null) ...
// 2. 递归左右
左结果 = func(root.left)
右结果 = func(root.right)
// 3. 结合左右结果,处理当前节点
...
}
2. 前序 / 后序 唯一区别
前序:先做事、再递归(翻转、遍历)
后序:先递归、再做事(深度、LCA)
3. 算法容器固定写法(背死)
-
存结果:
List<Integer> res = new ArrayList<>(); -
迭代栈:
Deque<TreeNode> stack = new ArrayDeque<>(); -
BFS队列:
Queue<TreeNode> queue = new ArrayDeque<>();
四、一句话每道题极简总结
-
中序遍历:左→根→右,迭代靠栈一路左到底
-
最大深度:左右最大值+1,标准后序分治
-
翻转树:每层交换左右,前序递归
-
对称树:两棵树交叉对比
-
LCA公共祖先:左右搜到就上抛,左右都有就是答案