跳到主要内容
约 18 分钟7 张卡

树与图搜索

图搜索是从一个或几个起点出发,沿着连接关系逐个访问能到达的节点。树是一种特殊的图,所以同一套方法两边都能用。搜索有两种基本顺序:深度优先搜索(DFS)沿一条路径走到底再回退,广度优先搜索(BFS)按离起点的远近一层层向外扩展。

这类题的代码通常不长,真正决定对错的是几个判断:节点和状态怎样定义,访问标记什么时候打,BFS 为什么能给出最短距离,以及搜索深度和每层宽度会占多少内存。

1. 面试核心​

先记住这几条,再读正文
  • 图用邻接表存储时,DFS 和 BFS 完整遍历都是 O(V+E),区别在访问顺序和峰值空间。
  • 二叉树按先左后右的顺序做分层 BFS,每层最后访问的节点组成右视图。卡 · BFS
  • 边权相同且为正时,多源 BFS 第一次到达某个节点时的距离,就是它到最近源点的距离。卡 · 多源 BFS
  • 有向图 DFS 中,遇到仍在当前路径上的灰色节点才说明有环,遇到已完成的黑色节点不算。卡 · 有向图三色判环
  • 判断二叉树是否平衡时,后序遍历让子树同时返回高度和平衡结果,每个节点只算一次,总时间 O(n)。卡 · 后序合并与树形结果
  • 最大路径和向父节点返回单臂,在当前节点比较双臂;全负树仍须保留一个实际节点作为非空路径。卡 · 二叉树最大路径和

2. 图的建模​

搜索之前,先要说清楚节点代表什么、从一个节点怎样走到另一个节点。显式图把邻接关系直接存下来,比如邻接表;隐式图不预先存边,搜索到某个状态时才按规则生成它的邻居。很多题目没有明说「图」,但都可以这样建模:

  • 二叉树节点的左右孩子是邻居。
  • 网格中可通行的上下左右位置是邻居。
  • 单词经过一次合法编辑,得到相邻状态。
  • 任务之间的先后依赖形成有向边。

建模时要确定这几件事:

  1. 一个状态包含哪些字段。
  2. 怎样生成合法邻居。
  3. 两个状态在什么条件下视为相同。
  4. 边是否有方向与权重。
  5. 搜索从一个起点还是多个起点开始。

其中第 3 条最容易出错。判断两个状态是否相同,要看所有影响后续选择的字段。比如迷宫里有钥匙和门时,状态要同时包含位置和手里的钥匙集合:站在同一个格子,带不同的钥匙能打开的门不同。如果只用坐标判断是否访问过,带着新钥匙回到老位置时会被误判为「已访问」而跳过,本来能走通的路就找不到了。

边的方向决定谁能到达谁,边权决定该用哪种最短路算法,具体见图。

3. DFS​

DFS 先沿一个分支走到底,走不下去再退回来处理其他分支。它适合这些任务:

  • 按前序、中序或后序遍历树。
  • 搜索连通分量,或判断路径是否存在。
  • 配合状态恢复,回溯枚举方案。
  • 按节点完成的顺序实现拓扑排序。

下面用 record 表示一棵普通二叉树(没有环,也没有两个父节点共享同一个子节点),递归输出前序遍历结果。record 是用一行声明一组数据字段的记录类语法,Java 16 起正式提供,Java 17、21 都可以用:

record TreeNode(int value, TreeNode left, TreeNode right) {}

static void preorder(TreeNode node, java.util.List<Integer> result) {
if (node == null) return;
result.add(node.value());
preorder(node.left(), result);
preorder(node.right(), result);
}

根是 1、左孩子 2、右孩子 3 时,结果是 [1,2,3]。代码先记录当前节点,再访问左子树、右子树,所以得到前序顺序。

在邻接表上做完整的 DFS,每个顶点和每条边都只处理常数次,时间是 O(V+E)。递归占用的空间取决于同时进行中的调用有多深。如果树退化成一条很长的链,每深入一层就多占一个栈帧,深度过大时会抛出 StackOverflowError。

3.1 显式栈​

显式栈是自己用一个栈容器保存待处理的节点,代替递归调用栈,这样深层搜索就不受线程栈大小的限制。下面仍然按前序访问同样的二叉树:

static java.util.List<Integer> preorderIterative(TreeNode root) {
java.util.List<Integer> result = new java.util.ArrayList<>();
java.util.Deque<TreeNode> stack = new java.util.ArrayDeque<>();
if (root != null) stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
result.add(node.value());
if (node.right() != null) stack.push(node.right());
if (node.left() != null) stack.push(node.left());
}
return result;
}

根为空时直接返回空列表。代码只把非空节点压栈,因为 ArrayDeque 不允许存 null,传入会抛出 NullPointerException。栈是后进先出的,所以先压右孩子、再压左孩子,弹出时左孩子在前,顺序才是前序。

这段代码的辅助空间是 O(h),h 是树高,返回的结果另占 O(n)。显式栈并没有省掉存储,待处理的节点还是要保存,只是从线程栈搬到了堆上的容器里,大小由堆内存决定,程序也能直接控制。在一般图上用显式栈搜索,还需要一个访问集合,空间上界是 O(V)。

4. BFS​

BFS 用队列按层处理节点:离起点近的一层处理完,才扩展下一层。它适合这些任务:

  • 按层遍历树。
  • 求无权图中的最少边数路径。
  • 找出距离起点 k 层的节点。
  • 求每个位置到最近源点的距离。

二叉树的右视图是从右侧看这棵树时能看到的节点,也就是每一层最右边的那个。下面按从左到右的顺序遍历每层,取每层最后一个节点:

static java.util.List<Integer> rightView(TreeNode root) {
java.util.List<Integer> result = new java.util.ArrayList<>();
java.util.Queue<TreeNode> queue = new java.util.ArrayDeque<>();
if (root != null) queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (i == levelSize - 1) result.add(node.value());
if (node.left() != null) queue.offer(node.left());
if (node.right() != null) queue.offer(node.right());
}
}
return result;
}

根是 1、左孩子 2、右孩子 3 时,右视图是 [1,3]。关键在 levelSize:每层开始时先记下队列里有多少个节点,这一轮只处理这么多个。处理过程中新加入的孩子都排在后面,留给下一轮,层与层之间就不会混在一起。

队列占用的空间是 O(w),w 是最大层宽。队列里存的是已经发现、还没处理的节点,这些节点也叫搜索前沿。很宽的树可能有 O(V) 个节点同时在队列里等待,所以宽度也是选算法时要考虑的内存约束。

5. visited 标记时机​

BFS 应该在节点入队时就标记为已访问,而不是出队时。图里有环或者多条路径时,同一个节点会被好几个前驱发现。入队时就标记,后来的前驱看到标记就不会再加入它;等到出队才标记,它在出队之前可能已经被加进队列好几次,重复项会浪费时间和空间。

下面的代码用整数给顶点编号,用 distance 数组同时记录距离和是否访问过,只展示扩展邻居的部分:

for (int next : graph[current]) {
if (distance[next] == -1) {
distance[next] = distance[current] + 1;
parent[next] = current;
queue.offer(next);
}
}

distance 初始全是 −1,表示没访问过;源点设为 0 后入队。普通 BFS 把每条边的成本都看作 1,按距离从小到大处理节点:距离为 d 的节点全部出队之前,距离为 d+1 的节点不会出队。所以一个节点第一次被发现时,得到的就是它的最少边数,后面再从别的路径发现它,距离只会相等或更大。parent 同时记下是从哪个节点走到它的。

在树上只沿左右孩子往下走、又没有共享子节点时,每个节点只会被发现一次,可以不用访问标记。但如果把树当成无向图,父节点也算邻居,就需要访问标记或者跳过来时的边,否则会沿原路走回去。

5.1 最短路径恢复​

distance 只说明要走多少步。要输出具体路线,就从目标出发沿 parent 一路往回走到源点,再把得到的序列反转。源点的 parent 可以设为 −1,作为停止标记;目标的 distance 仍是 −1,说明根本到不了。

每个节点只记一个 parent,所以只能恢复出一条最短路径。如果要所有最短路径,就要为每个节点保留所有距离比它少 1 的前驱,再枚举这些前驱的组合。最短路径的数量可能非常多,输出它们的成本也要算进总复杂度。

6. 多源 BFS​

多源 BFS 用来求每个位置到最近起点的距离,比如网格里每个空地到最近出口的距离。做法是把所有起点的距离都设为 0、一开始就全部入队,让它们在同一次搜索里一起向外扩展:

for (int source : sources) {
if (distance[source] == -1) {
distance[source] = 0;
queue.offer(source);
}
}

distance[source] == -1 的判断让重复的源点只入队一次,之后按普通 BFS 扩展。可以把它想象成所有起点同时向外一圈圈扩散:每条边的成本都是 1 时,队列里的距离按层递增,一个格子第一次被发现时,一定是最近的那个起点先到。这样一次搜索就得到所有位置的答案,不用从每个起点分别跑一遍 BFS。

在网格上,搜索时跳过障碍格和越界位置,到不了的格子保持 −1。每个格子最多入队一次,邻居固定是上下左右 4 个,所以总时间和空间都是 O(行数×列数)。

所有边权相同且为正时,最少边数乘以边权就是距离;边权不同时,要按条件选 0-1 BFS、Dijkstra 或 Bellman-Ford,见图。

7. 回溯​

枚举所有路径时,访问标记有两种不同含义:「当前这条路径用过」和「全局已经处理过」。路径标记在递归返回时要撤销,因为其他分支可能还要经过这个节点;全局的 visited 则一直保留,表示这个状态以后可以直接跳过。

两者混用就会出错:把路径标记当成全局标记永久保留,会漏掉经过同一节点的其他合法路径;该保留的全局标记被撤销了,又会重复扩展。加入、递归、撤销的完整机制见回溯。

8. 拓扑排序​

拓扑排序给有向无环图(DAG)的节点排一个顺序,让每条边的起点都排在终点前面。如果边表示「A 必须在 B 之前完成」,拓扑序就是一个满足所有依赖的执行顺序,所以它常用于构建顺序、课程依赖和任务调度。

入度是指向一个节点的边数。入度为 0,说明这个节点没有未满足的前置依赖,可以马上处理。Kahn 算法就是不断处理这样的节点:

  1. 统计每个节点的入度。
  2. 把所有入度为 0 的节点加入队列。
  3. 取出一个节点加入结果,并将每条出边终点的入度减一,相当于删除这些出边。
  4. 邻居入度降到 0 时,将它加入队列。
  5. 队列清空后,比较处理的节点数与 V,判断是否存在环。

为什么处理数小于 V 就说明有环?剩下的节点入度都大于 0,也就是每个都至少有一个前驱也在剩下的节点里。从任意一个剩余节点出发,沿着前驱一直往回走,节点个数是有限的,迟早会走到已经经过的节点,这就是一个环。反过来,所有节点都处理完时,每个节点都是在它的所有前驱之后才入队的,输出顺序满足每条边的依赖。

同一时刻可能有多个入度为 0 的节点,先处理哪个都行,所以拓扑序通常不唯一。题目要求字典序最小时,把队列换成最小堆(PriorityQueue),每次取编号最小的。用普通队列和邻接表实现时,时间是 O(V+E)。

8.1 有向图三色判环​

有向图也可以用 DFS 判环。关键是区分「还在当前递归路径上的节点」和「已经处理完的分支」,所以给节点标三种颜色:

  • 白色表示尚未访问。
  • 灰色表示仍在当前递归路径中。
  • 黑色表示该节点的所有出边已经处理完成。

遇到灰色邻居,说明当前路径之前从它出发走到了现在的节点,而这条边又指回它,于是构成环。遇到黑色邻居只说明走到了一个已经处理完的分支,从它出发的所有路径都检查过,没有回到当前路径,所以不构成环,继续检查其他边即可。只用「访问过/没访问过」两种状态就分不清这两种情况:0→1、0→2、2→1 没有环,但从 2 走到 1 时,1 已经访问过了。

无向图判环又不一样。在没有重复边的无向简单图里,同一条边从两端各会被看到一次,所以要排除走回父节点的那条边,否则每条边都会被误判成环。如果两个节点之间允许有多条边(平行边),就要按边的编号排除来时的那一条;如果把所有通向父节点的边都跳过,两条平行边构成的环就漏掉了。

9. 后序合并与树形结果​

很多树的问题可以这样解:先求出左右子树的结果,再在当前节点把它们合并。因为当前节点在两个子树之后处理,这叫后序合并。

以判断二叉树是否高度平衡为例,平衡要求每个节点的左右子树高度差不超过 1。直接的写法是在每个节点分别计算左右子树的高度,但高度本身就要遍历整棵子树,链状树上会累计 O(n²) 的重复工作。后序合并的做法是让每棵子树一次返回两样信息:平衡时返回高度,不平衡时返回失败标记 −1。

  • 空子树返回高度 0。
  • 任一子树返回 −1,或者左右高度差大于 1,当前节点也返回 −1。
  • 否则返回较高子树的高度加 1。

这样高度计算和平衡检查在一次遍历里完成,每个节点只合并一次,时间是 O(n),递归空间是 O(h)。

9.1 最近公共祖先​

最近公共祖先(LCA)是两个目标节点的公共祖先中离根最远的那个,这里一个节点也算自己的祖先。下面先假设两个目标是不同的节点并且都在树中,判断时比较节点身份(是否同一个对象),而不只比较节点值。

递归时,每个节点按下面的情况返回结果:

  1. 当前节点为空时,返回空。
  2. 当前节点等于任一目标时,直接返回它作为候选。
  3. 否则递归左右子树。若两侧都有结果,说明两个目标分别位于两侧,当前节点就是最近公共祖先。
  4. 若只有一侧有结果,就将该侧结果向上传递;两侧都为空时返回空。

如果一个目标正好是另一个的祖先,搜索遇到它时直接返回,不再往下找;它确实就是答案,因为它是自己的祖先,另一个目标又在它下面。这个推理依赖「两个目标都存在」:如果允许目标不在树里,只找到一个目标时也会把它当作候选返回,所以还要额外确认两个目标都存在。完整遍历的时间是 O(n),递归空间是 O(h)。

9.2 二叉树最大路径和​

二叉树最大路径和是在所有非空路径中找出最大的节点值之和。这里路径沿父子边连接,同一节点最多经过一次,可以不经过根;节点值可以为负。它需要区分两种结果:当前子树中已经形成的最大路径,以及还能接到父节点上的路径。

向父节点返回的路径必须从当前节点出发,最多沿一个孩子继续往下,这里称为单臂路径。如果把“左孩子—当前节点—右孩子”整条路径再接到父节点,当前节点就连上了三个方向,形成分叉,不再是一条路径。因此,向上只能返回 节点值 + max(0, 左单臂, 右单臂)。

当前子树的最终答案却可以同时使用两侧。在当前节点比较 节点值 + max(0, 左单臂) + max(0, 右单臂),再与左右子树内部的最佳答案取最大值。每条路径都有一个离根最近的节点,路径在这个节点最多连接左右两臂,所以这样逐个节点合并不会漏掉合法路径。

下面复用 DFS 的 TreeNode,用 PathResult 同时返回单臂收益 arm 与子树最佳值 best。输入仍须是一棵无环且无共享子节点的普通树;null 根被拒绝,因为本题要求非空路径。

record PathResult(long arm, long best) {}

static long maxTreePathSum(TreeNode root) {
if (root == null) throw new IllegalArgumentException("nonempty tree required");
return pathResult(root).best();
}

static PathResult pathResult(TreeNode node) {
if (node == null) return new PathResult(0, Long.MIN_VALUE);
PathResult left = pathResult(node.left());
PathResult right = pathResult(node.right());
long leftArm = Math.max(0, left.arm());
long rightArm = Math.max(0, right.arm());
long through = Math.addExact(Math.addExact((long) node.value(), leftArm), rightArm);
long arm = Math.addExact((long) node.value(), Math.max(leftArm, rightArm));
long best = Math.max(through, Math.max(left.best(), right.best()));
return new PathResult(arm, best);
}

根为 −10、左孩子为 9、右孩子为 20,20 的两个孩子为 15 和 7 时,答案是 15+20+7=42;这个结果留在 20 的子树里,不需要经过 −10。全树为负时,舍弃负孩子只表示不延长路径,当前节点本身仍被计入,所以 [-3,-1,-2] 这棵树的答案为 −1,不会错误返回空路径的 0。

空子树的 best 用 Long.MIN_VALUE 表示没有非空路径,只参与比较,不参与求和。求和使用 long 和 Math.addExact,超出 long 时抛出异常而不静默溢出。每个节点合并一次,总时间 O(n),递归及同时保留的结果空间 O(h)。这段递归实现适用于深度可容纳于调用栈的树;深链可能栈溢出,应按递归深度改为显式栈后序遍历,不能因算法是 O(n) 就忽略这一限制。

10. 常见问题​

10.1 DFS 和 BFS 时间一样,空间有什么区别?​

在邻接表上完整遍历,两者都是 O(V+E)。区别在于访问顺序:BFS 按距离一层层扩展,DFS 先沿一条路径走到底,所以占用空间的地方不同。估算空间时分别算三部分:等待处理的节点、当前路径的深度、访问集合。树很宽时 BFS 的队列会很大,路径很深时 DFS 的调用栈会很深。

10.2 递归太深为什么会出错,怎么办?​

10.3 可以直接在原网格上做访问标记吗?​

10.4 边有权重时还能用 BFS 吗?​

11. 面试题卡片​

12. 参考资料​

来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明