本文概览：二叉树方面的算法基本都要使用递归，本文系统讲解二叉树的结构和递归的三个核心问题（什么时候用递归、递归的开始与结束、怎么编写递归函数），并配合五道Hot 100入门题（中序遍历、最大深度、翻转二叉树、对称二叉树、二叉树的直径）进行说明

在刷 LeetCode Hot 100 的过程中，你会发现很多题目的标签里都有"二叉树"。而做二叉树的题目，基本上离不开一个工具——递归。很多人做二叉树的题觉得难，其实不是二叉树本身难，而是没搞懂递归。一旦理解了递归，二叉树的很多题目就变得顺理成章了

所以本文把二叉树和递归放在一起讲。先讲二叉树的结构，理解它的"自相似"特性；再讲递归，解决三个核心问题——什么时候用、从哪开始到哪结束、怎么编写；最后用五道 Hot 100 入门题（中序遍历、最大深度、翻转二叉树、对称二叉树、二叉树的直径）来实际演示

一、二叉树的结构

二叉树是一种每个节点最多有两个子节点的树形结构，两个子节点分别称为左孩子（left）和右孩子（right）

1
2
3
4
5
    1
   / \
  2   3
 / \   \
4   5   6

在这棵树中：

  • 节点 1 是根节点（root），它是整棵树的入口
  • 节点 2 是 1 的左孩子，节点 3 是 1 的右孩子
  • 节点 4、5、6 是叶子节点，它们没有子节点

二叉树的关键特征：子树也是二叉树

以节点 2 为根，它的左孩子是 4，右孩子是 5，这本身就构成了一棵完整的二叉树：

1
2
3
4
以节点2为根的子树：        以节点3为根的子树：
      2                       3
     / \                       \
    4   5                       6

这就是二叉树的递归结构：一棵二叉树由根节点、左子树、右子树组成，而左子树和右子树本身又是二叉树

更形式化地说，二叉树的定义本身就是递归的：

  • 一棵二叉树要么为空（null）
  • 要么由一个根节点 + 一棵左子树 + 一棵右子树组成，其中左子树和右子树也都是二叉树

这个特性非常重要——它是我们使用递归解决二叉树问题的根本原因。既然每个子树都是一棵独立的二叉树，那么对整棵树的操作，就可以自然地分解为：对根节点操作 + 对左子树做同样操作 + 对右子树做同样操作

以最大深度为例：

  • 整棵树的最大深度 = max(左子树深度, 右子树深度) + 1
  • 左子树深度 = max(左子树的左子树深度, 左子树的右子树深度) + 1
  • ...一直分解到空子树，深度为 0
1
2
3
4
5
    1           深度 = 3
   / \
  2   3         深度 = 2    深度 = 2
 / \   \
4   5   6       深度 = 1    深度 = 1    深度 = 1

每一层的深度都可以由其子树的深度推导出来，这就是递归的天然土壤

二、递归

二叉树方面的算法基本都要使用递归。这是因为二叉树本身的结构就是递归定义的——一棵二叉树由根节点、左子树、右子树组成，而左子树和右子树本身又是二叉树。这种"自相似"的结构，天然适合用递归来处理

但很多人对递归感到困惑，主要有三个问题：什么时候用递归、递归从哪开始到哪结束、怎么编写递归函数

下面逐一讲解，并在讲解过程中配合五道 Hot 100 入门题来说明

1. 什么时候使用递归

当问题可以被分解为"结构相同但规模更小"的子问题时，就可以用递归

所谓"结构相同"，就是子问题和原问题本质上是同一类问题，只是规模变小了。二叉树问题天然满足这个条件：

  • 对整棵树求深度 → 对左子树求深度 + 对右子树求深度 → 组合得到整棵树的深度
  • 对整棵树翻转 → 对左子树翻转 + 对右子树翻转 → 交换根的左右孩子
  • 对整棵树判断对称 → 比较根的左右子树是否镜像对称 → 继续递归比较下一层

每个子问题都是原问题在更小规模上的重现。识别这种"自相似"结构，就是判断是否使用递归的关键

更具体地说，当你发现**"解决当前层的问题，需要先解决下一层的同类问题"**时，递归就是正确的选择。比如：

  • 要求整棵树的深度，必须先知道左右子树的深度 → 递归
  • 要翻转整棵树，必须先翻转子树 → 递归
  • 要判断整棵树是否对称，必须先判断左右子树是否镜像对称 → 递归

反过来说，如果一个问题不能被分解为同结构的子问题，就不适合用递归。比如在二叉树中"找到第k小的元素"，单纯递归不够，还需要结合中序遍历的特性

2. 递归的开始与结束

很多人困惑：递归从哪里开始？到哪里结束？

核心认识：递归的"开始检查"和"结束条件"其实是同一回事

以最大深度为例，函数的第一行是：

1
if (root == null) return 0;

这个判断同时承担了两个角色：

  • 作为入口检查：当我们从父节点调用 maxDepth(root.left) 时，如果 root.left 是 null，说明这个方向没有子树，需要特殊处理
  • 作为终止条件：当递归不断深入，到达叶子节点的孩子（即 null）时，这个判断让递归停止并开始返回

为什么它们是同一回事？因为在递归的过程中，每个节点都会经历"首次进入函数"这一步。一个非空节点进入函数后，会继续往下递归；而一个空节点（null）进入函数后，就是递归的终点

用一个具体的例子来说明。假设我们计算 maxDepth(节点4)（4是叶子节点）：

1
2
3
4
5
6
maxDepth(4)
  → maxDepth(4.left) = maxDepth(null)    // 调用左子树
    → root == null, return 0             // 同一个判断，作为终止条件
  → maxDepth(4.right) = maxDepth(null)   // 调用右子树
    → root == null, return 0             // 同一个判断，作为终止条件
  → return max(0, 0) + 1 = 1

当我们调用 maxDepth(null) 时：

  • 从调用者的角度看：这是一个"新节点的入口检查"，发现这个节点是 null
  • 从递归的角度看：这是一个"终止条件"，递归不再继续深入

同一条 if (root == null) 判断，既是入口检查，也是终止条件

理解了这一点，就不再需要分别思考"递归从哪里开始"和"递归在哪里结束"，因为它们是同一个判断。你只需要想清楚一件事：遇到什么情况应该停止递归？ 这个停止条件，自然也就处理了"首次进入时节点为空"的情况

3. 怎么编写递归函数

编写递归函数有一个固定模式：

1
2
3
4
5
6
7
8
9
10
11
返回类型 递归函数(参数) {
    // 第一步：写结束条件（出口）
    if (终止条件) {
        return 基础值;
    }
    // 第二步：写递归调用（递的过程）
    左子树结果 = 递归函数(左参数);
    右子树结果 = 递归函数(右参数);
    // 第三步：组合结果并返回（归的过程）
    return 组合(左子树结果, 右子树结果, 当前节点);
}

第一步必须先写结束条件。这是最重要的原则。如果不先写出口，递归就会无限循环下去，导致栈溢出。而且正如前面分析的，结束条件也同时处理了"入口检查"的问题

第二步是递归调用。根据题意，决定需要递归处理哪些子问题。对于二叉树，通常是对左子树和右子树分别递归

第三步是组合结果。把子问题的结果和当前节点的信息组合起来，形成当前层的答案

这三步的顺序在不同题目中会有变化：

  • 先递归再处理（后序）：先拿到子树结果，再处理当前节点。如最大深度、翻转二叉树、直径
  • 先处理再递归（先序）：先处理当前节点，再递归子树
  • 穿插处理（中序）：递归左子树 → 处理当前节点 → 递归右子树。如中序遍历
  • 处理与递归交织：处理和递归交替进行。如对称二叉树

但无论哪种变化，出口条件永远在最前面

三、入门案例讲解

下面用五道 Hot 100 入门题来具体展示递归在二叉树问题中的应用。每道题都按照递归三步来分析：出口 → 递归调用 → 处理当前节点

五道题的 Java 实现代码如下（二叉树节点的定义统一为 TreeNode，包含 val、left、right 三个字段）

题目 出口条件 递归调用 处理当前节点
中序遍历 root == null → return left, right 添加值到集合（在两次递归之间）
最大深度 root == null → return 0 left, right max(left, right) + 1
翻转二叉树 root == null → return null left, right 交换左右孩子
对称二叉树 都null→true / 不匹配→false 外侧+内侧 比较值 + 递归比较镜像位置
直径 root == null → return 0 left, right 更新maxDiameter，返回深度

不同的是每道题"处理当前节点"的方式，但整体框架完全一样：出口判断 → 递归调用 → 处理当前节点

1. 二叉树的中序遍历

中序遍历题目

题目要求：按照"左子树 → 根节点 → 右子树"的顺序访问所有节点

递归三步分析：

  • 出口：if (root == null) return; — 空节点没有值可添加
  • 递归调用：对左子树和右子树分别中序遍历
  • 处理当前节点：在递归左子树之后、递归右子树之前，把当前节点的值加入集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> res = new ArrayList<>();
        inorderTraversal(root, res);
        return res;
    }
    private void inorderTraversal(TreeNode root, List<Integer> res){
        // 递归出口
        if(root == null){
            return;
        }
        // 添加左子树的值到集合
        if(root.left != null){
            // 递归调用
            inorderTraversal(root.left, res);
        }
        // 添加当前节点的值
        res.add(root.val);
        // 添加右子树的值到集合
        if(root.right != null){
            // 递归调用
            inorderTraversal(root.right, res);
        }
    }
}

这就是"中序"的含义——根节点在中间处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
        4
       / \
      2   6
     / \
    1   3

中序遍历过程：
1. 递归左子树(节点2)：
   - 递归左子树(节点1)：
     - 左为空，跳过
     - 添加 1
     - 右为空，跳过
   - 添加 2
   - 递归右子树(节点3)：
     - 左为空，跳过
     - 添加 3
     - 右为空，跳过
2. 添加 4
3. 递归右子树(节点6)：
   - 左为空，跳过
   - 添加 6
   - 右为空，跳过

结果：[1, 2, 3, 4, 6]

代码中的执行顺序就是：inorderTraversal(left) → res.add(root.val) → inorderTraversal(right)，正好对应"左→根→右"

这道题的递归属于穿插处理（中序）模式：先递归左子树，再处理当前节点，最后递归右子树。根节点的处理被夹在两次递归之间

2. 二叉树的最大深度

最大深度题目

题目要求：求二叉树的最大深度

递归三步分析：

  • 出口：if (root == null) return 0; — 空节点的深度为 0
  • 递归调用：分别求左子树和右子树的深度
  • 组合结果：max(左子树深度, 右子树深度) + 1 — 当前节点的深度 = 子树最大深度 + 1（自己这一层）
1
2
3
4
5
6
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
        3
       / \
      9  20
        /  \
       15   7

递归过程（展示"递"和"归"）：

递（向下调用）：
maxDepth(3) → maxDepth(9), maxDepth(20)
maxDepth(9) → maxDepth(null), maxDepth(null)     ← 到达叶子，准备"归"
maxDepth(20) → maxDepth(15), maxDepth(7)
maxDepth(15) → maxDepth(null), maxDepth(null)    ← 到达叶子
maxDepth(7) → maxDepth(null), maxDepth(null)     ← 到达叶子

归（向上返回）：
maxDepth(null) = 0  ← 终止条件
maxDepth(9) = max(0, 0) + 1 = 1
maxDepth(15) = max(0, 0) + 1 = 1
maxDepth(7) = max(0, 0) + 1 = 1
maxDepth(20) = max(1, 1) + 1 = 2
maxDepth(3) = max(1, 2) + 1 = 3

最大深度 = 3

这道题完美体现了递归的"自相似"特性：**每个节点都在问同一个问题——"我这棵子树有多深？"**，而答案都可以由子树的深度推导出来

属于先递归再处理（后序）模式：先拿到左右子树的深度，再计算当前节点的深度

3. 翻转二叉树

翻转二叉树题目

题目要求：翻转二叉树，使每个节点的左右子树交换

递归三步分析：

  • 出口：if (root == null) return null; — 空节点无需翻转
  • 递归调用：翻转左子树，翻转右子树
  • 处理当前节点：交换当前节点的左右孩子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    // 递归调用左子树和右子树
    invertTree(root.left);
    invertTree(root.right);
    // 交换根节点的左子树和右子树
    swap(root, root.left, root.right);
    return root;
}
private void swap(TreeNode root, TreeNode left, TreeNode right) {
    root.left = right;
    root.right = left;
}
1
2
3
4
5
6
翻转前：           翻转后：
      4                 4
     / \               / \
    2   7             7   2
   / \ / \           / \ / \
  1  3 6  9         9  6 3  1

为什么必须先递归翻转子树，再交换当前节点的左右孩子？

因为递归调用是靠 root.left 和 root.right 来找到子树的。如果先交换，那 root.left 就指向了原来的右子树，root.right 指向了原来的左子树，递归的方向就反了

正确的顺序：

  1. invertTree(root.left) — 翻转左子树（此时 root.left 还是原来的左子树）
  2. invertTree(root.right) — 翻转右子树（此时 root.right 还是原来的右子树）
  3. swap(root, root.left, root.right) — 交换左右孩子

代码中的 swap 方法只做简单的指针交换：

1
2
root.left = right;   // 原来的右孩子变成左孩子
root.right = left;   // 原来的左孩子变成右孩子

属于先递归再处理（后序）模式：先递归翻转左右子树，再交换当前节点的左右孩子。必须后序，否则递归方向会反

4. 对称二叉树

对称二叉树题目

题目要求：判断二叉树是否关于中心对称

递归三步分析：

这道题比前面几道复杂一点，因为不是单独处理一棵子树，而是要同时比较两棵子树是否镜像对称

  • 出口：
    • 两个节点都为 null → return true;（两边都空，对称）
    • 一个为 null 另一个不为 null，或值不同 → return false;（不对称）
  • 递归调用：比较 left.left 和 right.right（外侧），比较 left.right 和 right.left（内侧）
  • 处理当前节点：比较左右节点的值是否相等，且两侧递归结果都为 true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isSymmetric(TreeNode root) {
    if (root == null) {
        return true;
    }
    return recur(root.left, root.right);
}

private boolean recur(TreeNode left, TreeNode right) {
    // 递归出口
    if(left == null && right == null) {
        return true;
    }
    // 判断当前节点是否对称
    if(left == null || right == null || left.val != right.val) {
        return false;
    }
    // 递归调用左子树和右子树
    return recur(left.left, right.right) && recur(left.right, right.left);
}

镜像对称的关键在于"镜像"二字——左子树的左孩子应该和右子树的右孩子对称，左子树的右孩子应该和右子树的左孩子对称：

1
2
3
4
5
6
7
8
      1
     / \
    L   R        ← 要比较L和R是否镜像对称
   /\   /\
  a  b c  d

外侧对称：a vs d（L的左 vs R的右）→ recur(L.left, R.right)
内侧对称：b vs c（L的右 vs R的左）→ recur(L.right, R.left)

用一个具体的例子展示递归过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
      1
     / \
    2   2
   / \ / \
  3  4 4  3

recur(2, 2):
  - 2 != null, 2 != null, 2 == 2 ✓
  - 外侧：recur(2.left, 2.right) = recur(3, 3)
      - 3 != null, 3 != null, 3 == 3 ✓
      - recur(null, null) → true    （外侧的左 vs 右）
      - recur(null, null) → true    （外侧的右 vs 左）
      - return true && true = true
  - 内侧：recur(2.right, 2.left) = recur(4, 4)
      - 4 != null, 4 != null, 4 == 4 ✓
      - recur(null, null) → true
      - recur(null, null) → true
      - return true && true = true
  - return true && true = true

整棵树对称

如果某个位置不对称，比如左子树有个 3 但右子树对应位置是 null，那 left == null || right == null 就会命中，直接返回 false，短路后续的递归调用

这道题的出口条件比其他题复杂——需要同时判断两个节点，有三种情况（都空/一空一非空/都非空）。但本质上还是同一个思路：遇到什么情况应该停止递归？ 答案是：两个都空了就返回 true（对称到底了），不匹配就返回 false（不对称了）

5. 二叉树的直径

二叉树的直径题目

题目要求：求二叉树中任意两个节点间最长路径的边数

递归三步分析：

  • 出口：if (root == null) return 0; — 空节点的深度为 0
  • 递归调用：求左子树深度和右子树深度
  • 处理当前节点：经过当前节点的最长路径 = 左子树深度 + 右子树深度，用它更新全局最大直径；然后返回当前节点的深度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private int maxDiameter = 0;

public int diameterOfBinaryTree(TreeNode root){
    dfs(root);
    return maxDiameter;
}

// dfs查找最大深度
private int dfs(TreeNode root){
    if(root == null) {
        return 0;
    }
    // 递归调用左子树和右子树
    int leftDepth = dfs(root.left);
    int rightDepth = dfs(root.right);
    // 更新最大直径
    maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
    // 计算当前节点深度
    return Math.max(leftDepth, rightDepth) + 1;
}

这道题和最大深度非常相似，递归函数都在求深度。但多了一个关键点：直径不一定经过根节点

1
2
3
4
5
6
7
      1
     /
    2           直径 = 3（路径 5→3→2→4）
   / \
  3   4
 /
5

在上面的树中，经过根节点 1 的最长路径 = 左深度 + 右深度 = 3 + 0 = 3，但直径路径经过的是节点 2（5→3→2→4）。在这个例子中经过根节点的路径长度碰巧等于直径，但很多时候不是这样：

1
2
3
4
5
6
7
8
9
10
11
12
          1
         /
        2                直径 = 4（路径 5→3→2→4→6）
       / \
      3   4
     /     \
    5       6

经过节点1的路径 = 4 + 0 = 4
经过节点2的路径 = 2 + 2 = 4  ← 直径在这
经过节点3的路径 = 1 + 0 = 1
经过节点4的路径 = 0 + 1 = 1

关键理解：直径就是某个节点处左深度 + 右深度的最大值，这个节点可能不是根节点。所以我们需要在递归过程中持续更新最大直径，而不是只在根节点计算

代码中使用 maxDiameter 全局变量来记录：

1
2
3
4
// 每到一个节点，都计算"经过该节点的直径"并尝试更新最大值
maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
// 然后返回当前节点的深度，供上层使用
return Math.max(leftDepth, rightDepth) + 1;

递归过程示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
        1
       /
      2
     / \
    3   4
   /
  5

dfs(5): left=0, right=0
  → maxDiameter = max(0, 0+0) = 0
  → return max(0,0)+1 = 1

dfs(3): left=1, right=0
  → maxDiameter = max(0, 1+0) = 1
  → return max(1,0)+1 = 2

dfs(4): left=0, right=0
  → maxDiameter = max(1, 0+0) = 1
  → return max(0,0)+1 = 1

dfs(2): left=2, right=1
  → maxDiameter = max(1, 2+1) = 3  ← 在节点2更新了最大直径
  → return max(2,1)+1 = 3

dfs(1): left=3, right=0
  → maxDiameter = max(3, 3+0) = 3
  → return max(3,0)+1 = 4

最终直径 = 3（路径 5→3→2→4）

可以看到，最大直径在节点 2 处被更新为 3，这就是"直径不一定经过根节点"的体现

这道题和最大深度的递归结构几乎一样，唯一的区别是：最大深度只需要最终返回根节点的深度，而直径需要在每个节点都检查一次"经过这个节点的路径是不是最长的"