← 课程目录 🚀 从零到一
📐 学习维度 阶段8 · 第32章 数据结构与算法专题(leetcode 分类刷题指南) 🚀 从零到一 📚 课程目录 🏠 首页 🛤️ 学习路径

32.3 树与遍历:递归思维与 BFS/DFS

审校 2026-09-29 · 素材来源:raw 50 题单、raw 33 题型分类复盘
📑 本篇章节导航 (共10节,点击直达)
场景:树题为什么是递归试金石类比与定义:三种遍历顺序最小可跑示例:最大深度与层序遍历原理拆解:验证 BST 与公共祖先验证 BST 的两种标准写法树题的追问三连BST 的最近公共祖先:一次面试的完整弧线踩坑清单面试怎么问一句话总结

树的题单四道:最大深度(104)、层序遍历(102)、验证二叉搜索树(98)、最近公共祖先(236)。它们正好覆盖树的两大思维:DFS(深度优先,一条路走到黑再回头)与 BFS(广度优先,一层一层向外扩)。学完这一讲,「看见树题先想遍历方式」的条件反射就建立了。

场景:树题为什么是递归试金石

树本身就是递归定义的结构——每个子树都是一棵树。面试官用树题验证你能不能把大问题拆成「根+左右子树」的相同小问题。答不上递归的候选人,后面聊集合源码(第 6 章 HashMap 红黑树)时会被加倍追问——树题答得好,等于给源码章背书。

类比与定义:三种遍历顺序

把树想象成公司组织架构:前序(根左右)是先见总裁再见各部门——适合「自顶向下」构造或复制;中序(左根右)是先基层汇报再见领导——BST 中序遍历结果有序,这是 98 的钥匙;后序(左右根)是先把两个部门的事办完再汇总——适合「依赖子树结果」的计算,如求深度、算路径。层序(BFS)则是按职级一层层开会,用队列实现。

最小可跑示例:最大深度与层序遍历


// 104 最大深度:后序思维,子树深度+1
int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left),
                        maxDepth(root.right));
}

层序遍历换成队列视角:


// 102 层序遍历:队列按层消费,size 记录当前层节点数
List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();  if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();  q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();            // 固定本层数量
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode n = q.poll();
            level.add(n.val);
            if (n.left != null)  q.offer(n.left);
            if (n.right != null) q.offer(n.right);
        }
        res.add(level);
    }
    return res;
}

两个细节值钱:层序的 size 快照保证按层分组;深度的比较用 Math.max 而不是手写 if。

原理拆解:验证 BST 与公共祖先

验证 BST(98)的经典错误:只比较节点与直接子节点——[5,4,6,null,null,3,7] 中 3 比 6 小却在 5 的右子树里,错。正确做法两选一:中序遍历应严格递增(一个 prev 变量即可),或递归携带上下界(左子树所有值须小于根,右子树大于根,边界一路收紧)。最近公共祖先(236):后序递归,左右子树各找一次,两边都找到则当前节点就是答案;只找到一边则把结果向上传递——这个「左右汇聚」的写法同时覆盖 p、q 互为祖先的情况,不用特判。追问预案:「LCA 在数据库索引里对应什么」——B+ 树的分裂与范围查找(第 9.2 讲);「分布式系统里有对应物吗」——注册中心按路径寻祖(第 28.1 讲 Nacos 的层级模型)。树题答到这一层,就已经不是刷题,是把课程串成线了。

验证 BST 的两种标准写法

上下界收紧法(推荐现场写,一次成形):


boolean valid(TreeNode n, long lo, long hi) {
    if (n == null) return true;
    if (n.val <= lo || n.val >= hi) return false; // 越界即非法
    return valid(n.left, lo, n.val)       // 左子树上界=根
        && valid(n.right, n.val, hi);     // 右子树下界=根
}
// 调用:valid(root, Long.MIN_VALUE, Long.MAX_VALUE)

用 long 做边界是细节分:节点值可能取 int 极值,int 边界会误判。另一招中序递增:遍历中维护 prev,prev != null && prev.val >= cur.val 即返回 false——两招都要会,面试官问「还有别的方法吗」时无缝切换。

树题的追问三连

第一连·递归改迭代:中序不用递归怎么写?显式栈:一路压左到底,弹出访问,再转向右子树——这套「指针+栈」的写法是莫里斯遍历(O(1) 空间,临时改指针)的前置知识,答出栈版即达标。第二连·序列化:怎么把树存成字符串再还原?前序加 null 占位符(1,2,#,3),还原按同一顺序递归消费——追问「为什么不用中序」:中序缺少根的位置信息,无法唯一还原。第三连·路径族:路径总和(112/113)是「回溯+减法」——递归参数带 remain,到叶子判零;113 要收集路径正好复习 32.5 的收割拷贝。三连之后还有压轴一问:为什么需要红黑树——普通 BST 遇有序插入退化成链表,红黑树用变色与旋转保平衡,第 6 章 HashMap 树化与第 9.2 讲 B+ 树都是它的亲戚;能把树题答回数据结构章,是最漂亮的收口。

BST 的最近公共祖先:一次面试的完整弧线

同一道 LCA,普通二叉树用后序汇聚,BST 可以做得更巧——利用有序性迭代下潜:


TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) root = root.left;      // 都在左
        else if (p.val > root.val && q.val > root.val) root = root.right; // 都在右
        else return root;                  // 分叉点即祖先
    }
    return null;
}

这题适合展示「同题多解」的完整弧线:先答通用版(后序汇聚,适用任何二叉树),面试官追问「是 BST 呢」再滑出迭代版——顺着追问升级答案是面试里最舒服的节奏,比一次倒完所有存货高明。BST 带来的常数级优化还有一句可说:中序遍历即有序序列,所以「BST 第 k 小」(230)就是「中序遍历数到第 k 个」——树的题一旦挂上 BST 属性,答案几乎总要往「有序」上靠,这是审题雷达。

踩坑清单

面试怎么问

一句话总结

树题的钥匙是遍历顺序的选择:构造用前序、有序性用中序、汇总用后序、分层用层序——四道高频题各占一把钥匙,凑齐就是一棵技能树。