专题 07二叉树：递归思维的主战场

7.1树题的两种思考方式：遍历与分解

很多人写树题卡住，不是不会递归，是不知道「递归函数该返回什么」。 其实树题基本只有两种写法，先分清楚，后面每题都对号入座：

方式一：遍历（Traverse）——「一边走一边做事」

递归只是为了走到每个节点，真正的工作在「路过」时顺手做。函数返回值常常没用（返回 void 或一个标记）， 典型如「打印整棵树」「统计节点个数」「把每个节点值加 1」。你脑子里是一根指针在树上逛，逛到哪算到哪。

方式二：分解（Divide & Conquer）——「把问题拆给左右子树」

这是本章重点，也是面试 80% 树题的写法。核心想法：「我不管左右子树内部怎么长，只要它们各自把结果交给我，我合并一下就出答案」。 递归函数有返回值，返回值就是「以当前节点为根的子树，针对这个问题该给的答案」。

分解式思考模板（伪代码）：
  int f(节点 root):
      if root == null: return 基线值        // 空树的情况
      left  = f(root.left)                  // 左子树交出的答案
      right = f(root.right)                 // 右子树交出的答案
      return 用 left、right、root 算出的本层答案

本章的最大深度、翻转、对称、LCA 全是分解式。区分窍门：题目问的是「整棵树某个全局量」（最大深度、是否对称）， 那就用分解——让每个子树先报自己的局部答案，父节点汇总。

树节点的标准定义

力扣里树节点长这样，后面所有题都基于它：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}                          // 无参构造
    TreeNode(int val) { this.val = val; } // 只给值
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;                    // 给值 + 左右孩子
        this.left = left;
        this.right = right;
    }
}

用一个例子区分两种方式

同样一棵简单的树，两种写法写出来差别巨大。以「[1,2,3]」为例，比较「前序打印所有值」和「求节点总数」：

    1
   / \
  2   3

【遍历式：打印每个节点值】
void dfs(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val); // 路过就干活
    dfs(root.left);
    dfs(root.right);
}
→ 输出 1 2 3。函数无返回值，信息靠「副作用」（打印）带出。

【分解式：数节点总数】
int count(TreeNode root) {
    if (root == null) return 0;
    return 1 + count(root.left) + count(root.right); // 左右交答案，父层汇总
}
→ 返回 3。每个子树报自己的节点数，父节点 +1 合并。

看出区别了吗？打印那个函数「脑子里有个游客在走」，到哪打到哪；计数那个函数「自己不动，让左右孩子报数，最后加总」。 凡是结果能「由左右子树的同类结果合并得到」的，优先写分解式——它不需要全局变量，返回值一路把信息带上顶层， 既好写又好测。遍历式适合「副作用型」任务（打印、收集到外部 List、修改原树）。

7.2二叉树的最大深度（简单，力扣 104）

简单 核心：分解式入门

题意：返回树的最大深度（从根到最远叶子节点的节点数）。例：[3,9,20,null,null,15,7] 最大深度 3。

思路推导

用分解式想：一棵树的「最大深度」等于什么？等于「左子树的最大深度」和「右子树的最大深度」里较大的那个，再加 1（自己这一层）。 「左右子树最大深度」怎么来？递归调用自己就行了——同一个函数，丢给它左孩子、右孩子。 空节点（null）深度是 0，这是递归停下来的地方（base case）。

       3                  depth(3) = max(depth(9), depth(20)) + 1
      / \                 depth(9) = 0+1 = 1（左右都空）
     9  20                depth(20) = max(depth(15), depth(7)) + 1 = max(1,1)+1 = 2
       / \                depth(15)=1, depth(7)=1
      15  7
    → depth(3) = max(1, 2) + 1 = 3 ✓

参考代码

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;            // 空树深度 0（base case）
        int left = maxDepth(root.left);        // 左子树报深度
        int right = maxDepth(root.right);      // 右子树报深度
        return Math.max(left, right) + 1;      // 取较大者 + 自己这层
    }
}

复杂度

时间 O(n)：每个节点恰好访问一次。空间 O(n)：最坏退化为链表时递归栈深 n；平衡树 O(log n)。 为什么是 +1？因为上面的左右子树深度都还没算「当前节点本身」这一层，汇总时得补上。

7.3翻转二叉树（简单，力扣 226）

简单 核心：先递归后交换

题意：把整棵树的左右子树镜像翻转。例：根 4 的左孩子 2 和右孩子 7 互换，且各自子树也翻。

思路推导

分解式：翻转一棵以 root 为根的树，等于——先分别翻转它的左子树和右子树，再把 root 的 left、right 指针对调。 注意顺序：先「递归翻完下面」，再「在本层交换」。如果先交换再递归，交换后 left/right 已经互换，递归就翻错边了。 （其实先交换再递归也对，只要递归传的是交换后的引用；但「先递归后交换」最直观、最不易错。）

原:        4           翻左子树(2→1,3)  翻右子树(7→6,9)  交换 4 的左右
          / \          → 2:左右换        → 7:左右换        → 4.left=7, 4.right=2
         2   7         1   3            9   6
翻转后:    4
          / \
         7   2
        / \ / \
       9  6 3  1

参考代码

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;        // 空树直接返回
        TreeNode left = invertTree(root.left);  // 先翻左子树
        TreeNode right = invertTree(root.right); // 再翻右子树
        root.left = right;                     // 交换：左接翻好的右
        root.right = left;                     // 右接翻好的左
        return root;                           // 返回翻转后的根
    }
}

复杂度

时间 O(n)：每个节点访问一次。空间 O(n)（递归栈，最坏链表）。 为什么返回 root？因为翻转是「原地改」，改完把根交回去，上层就能接着接。

7.4对称二叉树（简单，力扣 101）

简单 核心：双树同步递归

题意：判断一棵树是否中心对称（左子树是右子树的镜像）。例：[1,2,2,3,4,4,3] 对称 → true；[1,2,2,null,3,null,3] → false。

思路推导

「对称」不是「左右相等」，是「左子树的左 = 右子树的右，左子树的右 = 右子树的左」——典型的镜像关系。 所以不能只比较 root.left 和 root.right 的值，要同时递归两棵树：一个走「外侧」（左的左 vs 右的右），一个走「内侧」（左的右 vs 右的左）。

写一个辅助函数 check(p, q) 判断「两棵树是否互为镜像」：

• 都为空 → 真；一个空一个不空 → 假；值不等 → 假；
• 否则递归 check(p.left, q.right) && check(p.right, q.left)。

参考代码

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return root == null || check(root.left, root.right); // 空树算对称
    }

    // 判断两棵树是否互为镜像
    private boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;   // 都空，这一支对称
        if (p == null || q == null) return false;  // 一个空一个不空，不对称
        if (p.val != q.val) return false;          // 值不同，不对称
        // 外侧配外侧，内侧配内侧
        return check(p.left, q.right) && check(p.right, q.left);
    }
}

复杂度

时间 O(n)：每个节点在比较中被访问（镜像对一一对应）。空间 O(n)（递归栈）。 为什么用「双树递归」而不是单树？因为对称性是两棵树之间的关系，单棵树无法表达「左子树的左」和「右子树的右」的对应，必须两个指针各走一边。

7.5二叉树的层序遍历（中等，力扣 102）

中等 核心：BFS + 按层出队

题意：返回「按层」的节点值列表。例：[3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]。

思路推导

层序 = 广度优先（BFS），用队列实现。难点在「怎么把同一层的节点分到一组」。 诀窍是：每一层开始前，先记下当前队列的长度 size——这个 size 就是「本层节点数」。 然后只出队 size 次，把这一层的节点收集起来；出队时把它们的孩子入队，孩子会自然排在「下一层」的队伍后面。 下一轮再取新的 size，如此一层层展开。

队列初始 [3]，size=1 → 出3，入9,20 → 本层[3]
队列 [9,20]，size=2 → 出9入null忽略；出20入15,7 → 本层[9,20]
队列 [15,7]，size=2 → 出15,7，无孩子 → 本层[15,7]
结果 [[3],[9,20],[15,7]]

注意：size 必须在每层循环外先取好。如果写在循环里 while (!q.isEmpty()) 每次都重新数， 新入队的孩子会被算进同一层，分层就乱了。

参考代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;                  // 空树返回空列表
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);                             // 根入队
        while (!queue.isEmpty()) {
            int size = queue.size();                  // ① 先取本层节点数
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {          // ② 只出队 size 次
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);   // 孩子入队，排到下一层
                if (node.right != null) queue.offer(node.right);
            }
            res.add(level);                            // 本层收集完，加入结果
        }
        return res;
    }
}

复杂度

时间 O(n)：每个节点入队出队各一次。空间 O(n)：队列最坏存满一层（满二叉树底层约 n/2）。 为什么必须「先 size 再循环」？因为循环内入队的孩子属于下一层，若实时取 size 会把它们算进当前层，分层失败。

为什么用「队列」而不是「栈」

层序要求「先遇到的节点先处理」——这正好是队列的 FIFO 语义。如果用栈（DFS 那套），会一头扎进最深的左子树， 出来的顺序是「根→左到底→回退」，变成深度优先，不是逐层。所以层序 = BFS = 队列，这是结构性绑定，不是个人喜好。 可以对比记忆：

再手推一遍 [3,9,20,null,null,15,7] 的 size 机制，重点看「size 怎么锁住当前层」：

初始队列 [3]，进入 while：size=1（锁定第1层只有3）
  循环1次：poll 3，level=[3]，入队 9,20 → 队列[9,20]
  res 加 [3]
下一轮：size=2（锁定第2层只有9,20，刚入队的15,7不算）
  循环2次：poll 9（入15,7→队列[20,15,7]），poll 20（入15? 已入；入7? 已入）→ level=[9,20]
  res 加 [9,20]
下一轮：size=2（锁定第3层：队列里正是[15,7]）
  循环2次：poll 15、poll 7，都无孩子 → level=[15,7]
  res 加 [15,7]
队列空，结束 → [[3],[9,20],[15,7]] ✓

关键就在每一轮开头那句 int size = queue.size()：它把「当前层有几个节点」快照下来， 循环里新入队的孩子虽然进了同一个队列，但不在本次 size 的计数内，于是自动归到下一轮。这个「快照」是分层的核心。

       3
      / \
     5   1         找 p=5, q=4（4在5的左子树2里）
    / \ / \
   6  2 0  8
     / \
    7   4

递归到 4：==q 返回 4
递归到 2：左null 右4 → 返回 4
递归到 5：左6返回null，右2返回4 → 一侧有 → 向上传 4？不对，5本身是p！
  实际上 5==p 直接返回 5；但 5 的右子树返回了 4（含 q）
  → 5 的左返回 null，右返回 4，且 5 自身是 p → 5 就是 LCA ✓

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 遇到空、或正好碰到 p/q，直接返回（p/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; // 分列两侧 → 当前是 LCA
        return left != null ? left : right;             // 只在一侧 → 把找到的传上去
    }
}