← 返回学习路线

SYSTEM

今日二叉树算法全集笔记(统一模板 \+ 每道题拆解 \+ 规律总结)

LeetCode题解
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公共祖先:左右搜到就上抛,左右都有就是答案