哈喽，大家好呀，我是蔚蓝，今天我们来聊聊二叉树。

你有没有过这种体验？打开 LeetCode，信心满满地点开一道二叉树的题，结果盯着屏幕半天，递归函数写了删、删了写，脑子里一团浆糊——这个返回值到底该是 int 还是 TreeNode？终止条件写 null 够不够？为什么别人的三行代码就能跑通，我写三十行还报空指针？

这不是你的智力问题，是你缺一个统一的思考框架。

我刷完二叉树 35 道经典题之后，把所有题目复盘了一遍，发现一个很有意思的事情：这些题看似五花八门，其实全在同一个套路里打转。而我将这个套路归纳为：递归五部曲。今天我把这五步拆开揉碎，配上七大题型，帮你掰开了，揉碎了讲清楚。

递归五部曲：别再凭感觉写代码了

很多人写递归就像蒙着眼睛炒菜，盐放多少全靠手感。递归五部曲就是给你一副精确的量杯：

第一步：确定递归函数的含义

这是最容易被跳过的一步。你拿到题目，别急着敲代码，先问自己一句话：「这个函数到底在算什么？」

比如求最大深度，maxDepth(root) 的含义是「以 root 为根的树的最大深度」。听起来像废话？但你往后看就知道，很多题卡住不是因为逻辑难，而是含义没定清楚。

第二步：确定入参和返回结构

入参决定了你递归过程中能访问到什么信息，返回值决定了你能把什么结果向上汇报。有些题需要返回一个数字，有些题需要返回一个节点，还有些题（比如打家劫舍 III）需要返回一个数组，把「偷」和「不偷」两种状态都带上去。

第三步：信任递归

这一步是心理建设，也是最重要的一步。

什么意思？假设你在求树的最大深度，你已经知道 maxDepth(root.left) 能正确返回左子树的深度，你也知道 maxDepth(root.right) 能正确返回右子树的深度。别去想它内部是怎么做到的，你只需要信任它，然后专注于当前节点该干什么。

这就像你在餐厅后厨，你是主厨，你让帮厨去切配菜。你不需要盯着他切的每一刀，你只需要相信切好的菜会出现在你面前，然后你来做你的那道工序。

第四步：确定递归的顺序

二叉树有三种经典遍历顺序，选哪一种取决于你的需求：

• 前序（中左右）：适合「从上往下」传递信息的场景，比如求深度
• 中序（左中右）：BST 的专属顺序，天然有序
• 后序（左右中）：适合「从下往上」汇总信息的场景，比如求高度

记住一个口诀：深度用前序，高度用后序，BST 搜中序。

第五步：确定单层递归的逻辑

走到这一步就简单了。你已经知道函数含义、入参返回值、遍历顺序，也信任了子问题的结果。现在只需要写当前节点这「一层」该做的事情——处理自己，然后交给下一层。

七大题型实战拆解

光说不练假把式。接下来我按照七大题型，逐个用五部曲拆给你看。每道题我只挑最核心的点讲，代码里该有的注释一个不少。

类型一：递归遍历——认识你的树

遍历是二叉树的地基。前序（中左右）、中序（左中右）、后序（左右中），三种顺序，一个模子。

拿前序遍历举例，五部曲走一遍：

1. 函数含义：遍历以 node 为根的子树，把节点值按前序顺序收集到 res 里
2. 入参和返回：入参是当前节点 + 结果列表，无返回值（直接往列表里塞）
3. 信任递归：preorder(node.left) 会正确处理左子树，我不关心细节
4. 遍历顺序：前序，所以先处理自己，再递归左右
5. 单层逻辑：把自己加入结果，然后左、右

1
2
3
4
5
6
7

// 前序遍历
void preorder(TreeNode node, List<Integer> res) {
    if (node == null) return;           // 终止条件：空节点不处理
    res.add(node.val);                   // 中 —— 先把自己搞定
    preorder(node.left, res);            // 左 —— 信任递归，交给左子树
    preorder(node.right, res);           // 右 —— 信任递归，交给右子树
}

你会发现，中序和后序的代码结构一模一样，唯一的区别就是 res.add(node.val) 放在哪个位置。遍历的三种顺序，本质就是「什么时候处理自己」的选择题。

类型二：属性求值——深度、高度和对称性

这类题是递归五部曲的最佳练手场，因为它们的含义定义特别清晰。

最大深度（LeetCode 104）——五部曲拆解：

1. 函数含义：maxDepth(root) 返回以 root 为根的树的最大深度
2. 入参和返回：入参一个节点，返回 int
3. 信任递归：maxDepth(root.left) 就是左子树的最大深度，maxDepth(root.right) 就是右子树的最大深度
4. 遍历顺序：后序！因为我需要先知道左右子树的深度，才能算当前节点的深度
5. 单层逻辑：取左右深度的较大值，加 1（算上自己这一层）

1
2
3
4
5
6

public int maxDepth(TreeNode root) {
    if (root == null) return 0;                        // 空树深度为 0
    int left = maxDepth(root.left);                     // 信任左子树的结果
    int right = maxDepth(root.right);                   // 信任右子树的结果
    return Math.max(left, right) + 1;                   // 当前层 = max(左, 右) + 1
}

三行核心代码，清清爽爽。

但你注意，最小深度（LeetCode 111）有个大坑。很多人直接把 max 改成 min 就交了，结果挂在 [1, 2] 这种测试用例上——左子树深度 0，右子树深度 1，min(0, 1) + 1 = 1，但正确答案是 2，因为根节点的左孩子不是叶子节点，你根本不能走那条路。

避坑指南：单侧子树为空时，只能走另一侧。这不是取 min 的问题，是你还没搞清楚「叶子节点」的定义——左右孩子都为空才叫叶子。

1
2
3
4
5
6
7
8
9

public int minDepth(TreeNode root) {
    if (root == null) return 0;
    int left = minDepth(root.left);
    int right = minDepth(root.right);
    // 坑就在这里：单侧为空，只能走另一侧
    if (root.left == null && root.right != null) return right + 1;
    if (root.left != null && root.right == null) return left + 1;
    return Math.min(left, right) + 1;
}

类型三：翻转与对称——动手改结构

翻转二叉树（LeetCode 226） 就是那道著名的「Homebrew 作者白板写不出来被拒」的题。说白了就是交换每个节点的左右孩子。

用五部曲思考：

1. 函数含义：翻转以 root 为根的二叉树
2. 入参和返回：一个节点，返回翻转后的根节点
3. 信任递归：invertTree(root.left) 已经把左子树翻好了，invertTree(root.right) 也一样
4. 遍历顺序：前序（先交换当前节点的左右，再递归处理子树）
5. 单层逻辑：交换左右指针

1
2
3
4
5
6
7
8
9
10
11

public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    // 先交换当前节点的左右孩子
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    // 再递归处理子树
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

对称二叉树（LeetCode 101） 的思路稍有不同——你需要同时比较两棵子树。函数含义变成「判断两棵子树是否镜像对称」，入参是两个节点。

1
2
3
4
5
6

boolean compare(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;        // 都空，对称
    if (left == null || right == null || left.val != right.val) return false; // 只有一个空或值不等
    // 外侧比外侧，内侧比内侧
    return compare(left.left, right.right) && compare(left.right, right.left);
}

注意这里的比较逻辑：左的左 和 右的右 比（外侧），左的右 和 右的左 比（内侧）。这就是「镜像」的含义——从外到内，完全翻转着比。

类型四：构造二叉树——从碎片到完整

这类题的经典模式是：给你两串遍历结果，让你还原出原来的树。

从中序与后序构造二叉树（LeetCode 106），五部曲：

1. 函数含义：根据中序和后序数组的一个区间，构造出一棵子树
2. 入参和返回：两个数组 + 各自的左右边界，返回构造出的根节点
3. 信任递归：左半区间能正确构造出左子树，右半区间能正确构造出右子树
4. 遍历顺序：后序的最后一个元素永远是根节点，用它在中序中切分左右
5. 单层逻辑：找到根节点，在中序中定位，切分区间，递归构造

1
2
3
4
5
6
7
8
9

TreeNode build(int[] post, int postL, int postR, int inL, int inR) {
    if (postL > postR || inL > inR) return null;
    TreeNode root = new TreeNode(post[postR]);       // 后序最后一个是根
    int idx = map.get(post[postR]);                    // 在中序中找到根的位置
    int rightLen = inR - idx;
    root.left = build(post, postL, postR - rightLen - 1, inL, idx - 1);
    root.right = build(post, postR - rightLen, postR - 1, idx + 1, inR);
    return root;
}

这道题的精髓在于区间的切割。后序数组里，左子树的区间怎么切、右子树的区间怎么切，全靠中序数组中根节点的位置来算。算错了就全盘崩溃。

一眼识别：遇到「给两种遍历序列构造二叉树」的题，套路都是——找根、切分、递归。前序+中序是第一个元素当根，后序+中序是最后一个元素当根，别的完全一样。

类型五：路径问题——从根走到叶

二叉树的所有路径（LeetCode 257），这道题的坑在于回溯。

五部曲分析：

1. 函数含义：从当前节点出发，收集所有到叶子节点的路径
2. 入参和返回：当前节点 + 当前路径字符串 + 结果列表
3. 信任递归：递归到左右子树时，它们会正确地把路径补全
4. 遍历顺序：前序，因为你要「从根往下走」
5. 单层逻辑：把当前节点加进路径，到叶子就存结果，否则继续递归

1
2
3
4
5
6
7
8
9

void traversal(TreeNode node, String path, List<String> res) {
    path += node.val;
    if (node.left == null && node.right == null) {
        res.add(path);          // 到叶子了，保存路径
        return;
    }
    if (node.left != null) traversal(node.left, path + "->", res);
    if (node.right != null) traversal(node.right, path + "->", res);
}

这道题的巧妙之处在于，因为 Java 字符串是不可变的，每次 path + "->" 都产生了新对象，所以天然不需要手动回溯。但如果你换成 StringBuilder，那就必须手动删掉追加的部分——这就是回溯的经典操作。

类型六：二叉搜索树（BST）——自带排序的树

BST 的性质一句话概括：左小右大，中序有序。这个性质让你在很多题上可以简化判断。

验证 BST（LeetCode 98）——中序遍历判断是否严格递增：

1
2
3
4
5
6
7
8

TreeNode pre = null;
public boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    if (!isValidBST(root.left)) return false;
    if (pre != null && pre.val >= root.val) return false;  // 不是严格递增
    pre = root;                                              // 更新前驱
    return isValidBST(root.right);
}

这道题用了一个 pre 指针记录中序遍历的前驱节点。BST 的中序遍历一定是严格递增的，只要你发现当前节点不比前驱大，直接返回 false。

BST 的最近公共祖先（LeetCode 235） 更是优雅：

1
2
3
4
5
6
7
8

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // p 和 q 都比 root 小，答案在左子树
    if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
    // p 和 q 都比 root 大，答案在右子树
    if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
    // 一个大一个小（或等于），说明分叉了，root 就是公共祖先
    return root;
}

BST 的 LCA 比「普通二叉树的 LCA（LeetCode 236）」简单很多，因为你不需要遍历完整棵树，直接根据大小关系砍掉一半的搜索空间。这就是 BST 自带「导航」的威力。

类型七：公共祖先——自底向上的汇报

普通二叉树的最近公共祖先（LeetCode 236） 是二叉树里思维难度最高的一道题之一。

五部曲走一遍：

1. 函数含义：在以 root 为根的树中，找 p 和 q 的最近公共祖先
2. 入参和返回：root、p、q，返回找到的祖先节点（或者 p/q 本身）
3. 信任递归：lowestCommonAncestor(root.left, p, q) 能在左子树找到目标，右子树同理
4. 遍历顺序：后序！必须先知道左右子树的搜索结果，才能判断当前节点是不是祖先
5. 单层逻辑：左右都找到了 → 当前就是 LCA；只找到一边 → 返回找到的那一边

1
2
3
4
5
6
7

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 ? left : right;                         // 只有一边有结果，往上传递
}

这道题的精髓在第 5 行：if (left != null && right != null) return root。这意味着 p 和 q 分别在当前节点的两棵子树中，当前节点就是它们的最近公共祖先。

这也是「后序遍历」最典型的应用——你需要「先收集子树的信息，再做判断」，无法提前返回。

一张表总结

题目速查表

下面是文章中涉及的所有 LeetCode 题目，按七大题型分类，方便你按需跳转练习：

递归遍历

层序遍历

属性求值

翻转与对称

构造二叉树

二叉搜索树（BST）

公共祖先

碎碎念

刷二叉树，最怕的不是题目难，而是你没有统一的思考框架。每道题都从头开始「感觉应该这样写」，写了删、删了写，效率低到令人崩溃。

递归五部曲就是你的「算法量杯」。拿到任何一道二叉树的题，别急着写代码，先按五步走一遍：函数含义是什么、入参返回值怎么定、我能不能信任子问题的结果、该用前序还是后序、当前层要做什么。五步走完，代码基本就出来了。

你回头看看上面每一道题，是不是都是这个套路？35 道题，一个模子。

递归从来不是玄学，它只是一种 「定义清楚、信任子问题、只管当前层」 的思维方式。一旦你接受了这种思维，二叉树的题目就不是在考你算法能力了，而是在考你够不够冷静。

以上，希望能帮你少走点弯路。刷题路上，一起加油 💪