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

这一课你将能做到

1. 区分 DFS（前中后序）和 BFS（层序），并说出各自的代码骨架
2. 用递归和层序两种方式求二叉树最大深度
3. 利用「后序遍历」的返回值求最近公共祖先（LCA）

为什么要学

树形结构是现实世界层级关系的直接映射：组织架构、目录文件、评论盖楼、MySQL 的 B+ 树索引、Redis 的压缩列表与哈希渐进扩容背后也有结构分层。学会树，不只是会做树题——递归这一最重要的编程思维，在树上最容易真正开窍。

初学者往往怕递归：函数自己调自己，像套娃。其实写树的递归只有一个心法：别钻进递归里，只关心「当前节点这一层该做什么」，并假设子节点的结果已经有人给你算好。本课三个必考题——层序遍历、最大深度、最近公共祖先——恰好展示 BFS、简单 DFS、带信息返回的 DFS 三种递进套路。

先建立图像

节点定义：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

        3
      /   \
     9     20
          /  \
         15   7

四种遍历（以这棵树为例）：

遍历	顺序	结果
前序 DFS	根 → 左 → 右	3,9,20,15,7
中序 DFS	左 → 根 → 右	9,3,15,20,7
后序 DFS	左 → 右 → 根	9,15,7,20,3
层序 BFS	按层从上到下	[3],[9,20],[15,7]

经验：要收集「当前节点」信息用前序；要等子节点有结果后再决策用后序；按层处理用队列 BFS。

跟着做

步骤 1：LeetCode 104「二叉树的最大深度」（简单）

根节点到最远叶节点的最长路径上的节点数。

递归定义法：一棵树的最大深度 = 1（当前节点自己）+ 左右子树深度的较大者。

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return 1 + Math.max(leftDepth, rightDepth);
    }
}

逐点讲：这就是后序思想——先从两个子节点拿到深度，再算当前节点的答案。时间 O(n)（每个节点访问一次），空间 O(h)（h 为树高，递归栈所用；最坏斜树为 O(n)）。

步骤 2：LeetCode 102「二叉树的层序遍历」（中等）

按层返回节点值，每层一个列表。

BFS 用队列。关键技巧：每轮开始先记下当前队列长度（即这一层的节点数），只处理这么多，处理中产生的下一层节点自然留在队列里等下一轮。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<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++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            result.add(level);
        }
        return result;
    }
}