树的题单四道:最大深度(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(98)的经典错误:只比较节点与直接子节点——[5,4,6,null,null,3,7] 中 3 比 6 小却在 5 的右子树里,错。正确做法两选一:中序遍历应严格递增(一个 prev 变量即可),或递归携带上下界(左子树所有值须小于根,右子树大于根,边界一路收紧)。最近公共祖先(236):后序递归,左右子树各找一次,两边都找到则当前节点就是答案;只找到一边则把结果向上传递——这个「左右汇聚」的写法同时覆盖 p、q 互为祖先的情况,不用特判。追问预案:「LCA 在数据库索引里对应什么」——B+ 树的分裂与范围查找(第 9.2 讲);「分布式系统里有对应物吗」——注册中心按路径寻祖(第 28.1 讲 Nacos 的层级模型)。树题答到这一层,就已经不是刷题,是把课程串成线了。
上下界收紧法(推荐现场写,一次成形):
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+ 树都是它的亲戚;能把树题答回数据结构章,是最漂亮的收口。
同一道 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 属性,答案几乎总要往「有序」上靠,这是审题雷达。
树题的钥匙是遍历顺序的选择:构造用前序、有序性用中序、汇总用后序、分层用层序——四道高频题各占一把钥匙,凑齐就是一棵技能树。