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

这一课你将能做到

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;
    }
}

逐点讲：忘记快照 size、直接 while 到队列空，就会把所有层混在一起。时间 O(n)，空间 O(n)（队列最大宽度，满二叉树约 n/2）。

步骤 3：LeetCode 236「二叉树的最近公共祖先」（中等）

给定两个节点 p、q，找它们最深的共同祖先（节点自己也算自己的祖先）。

递归函数定义为「在以 root 为根的树里，返回 p、q 的最近公共祖先；如果只找到 p 或只找到 q，就返回找到的那个；都没找到返回 null」。站在当前节点分情况：

1. root 本身是 p 或 q：它就是答案（另一节点若在子树中，root 必然是公共祖先）。
2. 左右子树的返回值都非空：p、q 分居两侧，root 是 LCA。
3. 只有一侧非空：把那一侧结果往上交。

class Solution {
    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; // p、q 分居左右
        }
        return left != null ? left : right;
    }
}

逐点讲：这是后序返回值最经典的用法——当前节点的决策完全依赖两个子调用结果。时间 O(n)，空间 O(h)。

讲清楚要点

1. 递归题先写函数「定义」：输入是什么、返回什么、语义一句话。定义清晰，函数体只是在当前层兑现这个定义，LCA 尤其如此。
2. base case 通常是 null：空树返回什么（0、false、null），决定整个递归的地基。
3. 前序 vs 后序看信息流向：信息从根下发用前序；信息从子节点汇总用后序。深度和 LCA 都是后序。
4. BFS 的层界靠队列长度快照：这是所有按层变体（锯齿层序、层平均值、右视图）的统一入口。
5. 空间先说树高 h 而不是直接写 O(n)：平衡树是 O(log n)，只有斜树才退化到 O(n)，这样回答更精确。

你可能会懵的地方

• 递归调用时我脑子里展开不了全部层级，怎么办？ 不需要展开。人脑不该模拟计算机。你只验证两件事：base case 对不对；假设子调用正确，当前层的拼接逻辑对不对。数学归纳法保证整体正确。

• LCA 里如果 p 或 q 不在树中呢？ 本题题目保证两节点都存在。若不保证，需要先判断「找到的是不是真两个」，常见做法是先搜索确认存在，再跑 LCA；直接套本代码会把单个存在的节点误返回。

• 中序遍历对二叉搜索树（BST）有什么特殊意义？ BST 的中序遍历严格升序，所以「验证 BST」「BST 中第 k 小」都可以先想到中序序列。

• 层序遍历能不能用递归写？ 能，给 DFS 传一个「层数」参数，按层往对应列表里加。但这本质是用 DFS 模拟，队列 BFS 更贴合「按层」直觉。

• 什么是「锯齿形层序遍历」？ LeetCode 103：偶数层正向、奇数层反向，在 102 模板上按层翻转列表即可，是最常见的现场变形。

错法对照

错法	问题	正解
递归里不写 root == null 判断	第一波空节点访问就 NPE	base case 先行
深度写成累加全局变量不回溯	多个分支互相污染	用返回值表达，或回溯时减回
层序不固定 size	所有层混在一起	进 while 先快照 queue.size()
子节点入队不判空	队列混入 null，poll 后 NPE	入队前判 != null
LCA 先判左右再判 root==p	可能错过节点自身即答案的情况	开头合并判断三种 base

卡点急救

1. 递归写两行就卡住：把问题改写成「对子树的提问」。最大深度 = 问左子树多深、右子树多深；能用一句话提问，就能写成递归函数。
2. LCA 答案时对时错：检查三种分支是否齐全——root 即目标、左右都非空、单侧非空，漏掉任何一种都会在特定位置结构下出错。
3. 层序输出格式不对（要每层独立列表）：确认 size 在循环外取一次而不是每轮动态取，for 循环严格消费 size 个节点。

面试常问

• 给你一棵二叉树，怎么判断它是不是二叉搜索树？ 上下界递归法：每个节点必须落在 (下界, 上界) 内；进入左子树把上界收为当前值，进入右子树把下界抬为当前值。也可中序遍历检查序列是否严格递增。LeetCode 98。

• 二叉树的右视图怎么做？ 层序 BFS，每层最后一个节点入结果；或 DFS 按「根右左」顺序，每层第一个访问到的节点入结果。本质都是 102 模板的一层窗户纸（LeetCode 199）。

• 递归太深会栈溢出，工程上怎么办？ 改为显式栈 / 队列的迭代写法（栈模拟 DFS、队列模拟 BFS），内存受堆管理而不受线程栈大小限制。处理超深目录树、超大组织树时必须如此。

自测三问

1. 前序、中序、后序的区别是什么？哪一种天然适合「汇总子节点结果」？
2. 层序遍历为什么要在每层开始时快照队列长度？
3. LCA 递归函数返回值有哪三种语义？当前节点根据什么决定自己是不是答案？

小结一句话

树题就是「站在当前层、信任子调用」：深度与 LCA 靠后序返回值汇总，层序靠队列长度快照分层，递归定义先于代码。

延伸

• 巩固练习：LeetCode 103 二叉树的锯齿形层序遍历、LeetCode 98 验证二叉搜索树、LeetCode 199 二叉树的右视图
• 在本站在线判题平台提交，测试空树、单节点、完全斜树三类边界
• 下一课预告：堆与优先队列——快速取到最大或最小，解决 Top K 与数据流中位数