树与图搜索

树与图搜索从一个节点或状态出发，沿连接关系访问可达的邻居。深度优先搜索（DFS）沿一条路径深入后回退，广度优先搜索（BFS）则逐层扩展。本文先说明怎样建模和遍历，再讲访问标记、路径恢复、多源搜索与判环，最后介绍树的子问题合并。

选择搜索方法时，要结合状态身份和访问标记判断是否会重复扩展。本文也会解释 BFS 得到最短距离的条件，以及搜索深度和每层宽度对空间的影响。

1. 面试核心

先记住这几条，再读正文

• 遍历成本。 图用邻接表存储时，DFS 和 BFS 完整遍历的时间复杂度均为 O(V+E)，但访问顺序与峰值空间不同。
• 右视图。 对二叉树按先左后右的顺序做分层 BFS 时，每层最后访问的节点组成右视图。卡 · BFS
• 多源 BFS。 边权相同且为正时，多源 BFS 第一次到达某个节点的距离，就是它到最近源点的距离。卡 · 多源 BFS
• 有向图判环。 对有向图做 DFS 时，若遇到当前路径中标为灰色的节点，就能确认图中存在环。卡 · 有向图三色判环
• 后序状态合并。 判断二叉树是否平衡时，后序遍历可合并左右子树的高度与平衡状态，让每个节点只计算一次。卡 · 后序合并与树形结果

2. 图的建模

搜索前，需要先说明节点代表什么、怎样从一个节点走到另一个节点。显式图直接保存邻接关系，隐式图则在搜索时按规则生成邻居。

可以用以下例子理解节点与边：

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

建模时，需要明确以下条件：

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

状态身份需要覆盖影响后续选择的字段。比如，带钥匙的寻路状态应同时包含位置与钥匙集合。同一位置拿到不同钥匙后，可以通过的门不同，只记录坐标就会把这些状态混在一起。

边方向决定可达关系，边权决定最短路算法的选择，具体见图。

3. DFS

必会卡 · 二叉树右视图如何用 BFS 或 DFS 实现？

DFS 先沿一个分支走到底，再返回处理其他分支。它适合以下任务：

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

下面用 record 表示无环、无共享子节点的二叉树，并递归输出前序结果：

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]。代码先记录当前节点，再访问左、右子树，因此得到前序顺序。record 是 Java 16 正式提供的记录类语法，用于声明一组数据字段；本文使用 Java 21。

邻接表的完整 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。栈按后进先出的顺序弹出，所以先压右孩子，再压左孩子，就能先访问左侧。

此二叉树实现的辅助空间为 O(h)，h 表示树高；返回结果另占 O(n)。显式栈把待处理节点保存在堆上的容器中，程序可以直接控制保存与恢复。它仍需要存储这些节点，只是省去了逐层递归调用。一般图还需要访问集合，空间上界为 O(V)。

4. BFS

必会卡 · 二叉树右视图如何用 BFS 或 DFS 实现？

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 如何恢复一条最短路径？

图中有环或多条路径时，同一状态会被不同前驱发现。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 把每条边视为单位成本，按距离从小到大处理节点。因此，首次发现邻居时就得到它的最短边数，同时用 parent 记录从哪个节点走到它。

只沿左右孩子访问、且无共享子节点的树，可以省略 visited。若把树转成无向图，父节点也成为邻居，就需要访问标记或排除父边，避免沿原边返回。

5.1 最短路径恢复

距离只能说明需要走多少步。若要输出具体路线，就从目标沿 parent 回走到源点，再反转序列。源点 parent 可设为 −1，作为停止标记；目标 distance 为 −1 时，则表示无可达路径。

每个节点只记录一个 parent，就只会恢复一条最短路径。若需要全部最短路径，应保留所有距离比当前节点少 1 的合法前驱。随后枚举前驱组合，输出数量也要计入总成本。

6. 多源 BFS

必会卡 · 如何求网格各位置到最近起点的距离？

多个起点都可以作为出发位置时，需要求的是到最近起点的距离。把所有不同源点设为距离 0 并同时入队，就能在一次搜索中让它们共同向外扩展：

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

重复源点只加入一次，随后按普通 BFS 扩展。单位边权下，队列按距离层次递增，所以某个格子首次被发现时，得到的就是最近源点距离。这省去了为每个目标分别运行 BFS 的重复工作。

在网格中，搜索跳过阻塞格和越界位置，无法到达的格保留 −1。每个格子至多入队一次，上下左右的邻居数量固定，所以总时间和空间为 O(行数×列数)。

边权相同且为正时，可将最少边数乘以边权得到距离；权重不同时，按条件选择 0-1 BFS、Dijkstra 或 Bellman-Ford，见图。

7. 回溯

枚举路径时，要区分“当前路径用过”和“全局已经处理过”。当前路径标记在递归返回时撤销，让其他分支还能选择该节点；全局 visited 则保留，表示该状态后续可跳过。

把路径标记永久保留会漏掉合法路径，过早撤销全局标记则会造成重复扩展。加入、递归和撤销的完整机制见回溯。

8. 拓扑排序

必会卡 · 有向图遇到已访问节点就是环吗，Kahn 如何判环？

拓扑排序为有向无环图安排一个顺序，让每条边的起点都排在终点之前。它适合构建顺序、课程依赖和任务调度。

入度是指向一个节点的边数。Kahn 算法把入度为 0 的节点视为前置依赖已经满足，按以下步骤处理：

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

若处理数小于 V，剩余子图就含有环。因为剩余每个节点都有前驱，沿前驱反复回走，在有限节点中必然遇到重复节点。若所有点都处理完，输出顺序就满足每条边的依赖。

多种零入度选择可产生不同拓扑序。要求字典序最小时，用最小堆管理零入度候选。普通邻接表队列实现为 O(V+E)。

8.1 有向图三色判环

有向图还可以在 DFS 中判环。这里要区分当前路径与已经完成的分支，所以使用三种颜色：

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

遇到灰色邻居时，当前路径已经从它走到当前节点，新边又返回它，因此构成环。遇到黑色邻居只表示到达已完成分支，应继续检查其他边。比如，0→1、0→2、2→1 无环，但会重复遇到 1。

无向简单图需要排除返回父节点的边，因为同一条边会从两端各看到一次。若允许两个节点间有多条边，也就是平行边，就要按边 ID 排除父边。否则，把所有通向父节点的边都跳过，会漏掉环。

9. 后序合并与树形结果

必会卡 · 如何在线性时间判断二叉树是否高度平衡？卡 · 二叉树最近公共祖先如何合并结果，目标缺失时怎么办？

树的问题可以先求左右子树的结果，再由当前节点合并，这就是后序处理。比如，检查高度平衡时，每个节点都要求左右子树高度差至多为 1。

让空子树返回高度 0，其他子树返回高度或失败标记 −1。任一子树失败，或左右高度差大于 1，就向上返回 −1。否则返回最大子树高度加 1。这样，高度计算和平衡检查就在一次遍历中完成。

每个节点只合并一次，时间为 O(n)，递归空间为 O(h)。若在每个节点重新计算两侧高度，链状树会累计 O(n²) 工作。

9.1 最近公共祖先

最近公共祖先是两个目标的公共祖先中，深度最大的节点。这里允许一个节点作为自己的祖先。下面先假设两个不同目标都存在，并按节点身份区分，而不只比较节点值。

递归合并时，按以下情况返回结果：

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

若一个目标正是另一个的祖先，遇到它时直接返回，就得到应选的祖先。若允许目标缺失，还需额外核验两个目标是否都存在，否则只找到一个目标也会向上返回候选。完整遍历时间为 O(n)，递归空间为 O(h)。

10. 常见问题

下面集中说明遍历成本、递归深度和输入修改的边界，以及边权变化后的选择。

10.1 DFS 与 BFS 的成本

邻接表完整遍历的 DFS 与 BFS 都为 O(V+E)。BFS 按距离扩展，DFS 先沿一条路径深入，所以访问顺序和峰值空间不同。估算空间时，分别计算等待处理的节点、活动路径和访问集合。树上若每层很宽，BFS 队列会很大；若路径很深，DFS 调用栈会很大。

10.2 递归深度

10.3 原地访问标记

10.4 带权最短路径

11 · 面试题卡片

先想答案，再翻面先在心里答一遍，再点开卡片对照参考回答。卡片之间可以左右切换，看完会回到这里。

逐张翻看 6 张 →

BFS必会

二叉树右视图如何用 BFS 或 DFS 实现？

字节跳动

考察 1 点 · 相关 §4 §3

多源 BFS必会

如何求网格各位置到最近起点的距离？

字节跳动

考察 1 点 · 相关 §6

有向图三色判环必会

有向图遇到已访问节点就是环吗，Kahn 如何判环？

本站自测

考察 1 点 · 相关 §8.1 §8

后序合并与树形结果必会

如何在线性时间判断二叉树是否高度平衡？

本站自测

考察 1 点 · 相关 §9

最短路径恢复必会

BFS 如何恢复一条最短路径？

本站自测

考察 1 点 · 相关 §5.1

最近公共祖先必会

二叉树最近公共祖先如何合并结果，目标缺失时怎么办？

本站自测

考察 1 点 · 相关 §9.1

11.1 二叉树右视图如何用 BFS 或 DFS 实现？

出现公司：字节跳动

考察重点：解释 BFS 的层边界与 DFS 的右侧优先顺序，并比较两种方法的时间和峰值空间。

相关内容：BFS、DFS。

参考回答

BFS 可以按左先右后的顺序取每层最后一项，DFS 则可先走右侧，记录每个深度首次访问的节点。

BFS 在每层开始时保存队列大小，处理完这批节点后再进入下一层，层边界就不会混淆。DFS 从深度 0 开始，当当前深度等于结果长度时，说明首次到达这一层，就记录节点。

两者各访问每个节点一次，时间为 O(n)。BFS 辅助空间为 O(w)，w 是最大层宽；DFS 递归空间为 O(h)，h 是树高。深树使用递归时还要考虑线程栈容量。

11.2 如何求网格各位置到最近起点的距离？

出现公司：字节跳动

考察重点：解释多个源点同时入队为何只需遍历一次，并说明单位边权和入队标记的作用。

相关内容：多源 BFS。

参考回答

将全部不同源点设为距离 0 并同时入队，再运行一次 BFS，就能求出单位边权下的最近起点距离。

每次向上下左右扩展，首次发现邻居时写入当前距离加 1，并立即标记。所有源点共同按距离层次扩展，所以更短的路线会更早到达。阻塞格与越界位置直接跳过，未到达的格保留 −1。

每个格子至多入队一次，总时间与空间为 O(行数×列数)。移动成本改变时，需要按边权范围改用 0-1 BFS、Dijkstra 等方法。

11.3 有向图遇到已访问节点就是环吗，Kahn 如何判环？

出现公司：暂无已核验的公开来源（本站自测）

考察重点：区分当前活动路径与已完成分支，并解释 Kahn 剩余节点的入度为何能用于判环。

相关内容：有向图三色判环、拓扑排序。

参考回答

有向 DFS 遇到当前路径中的灰色节点，才能由这条边确认环；Kahn 则用处理节点数是否小于 V 判环。

黑色节点已经完成，重复到达它本身无法说明有环。比如 0→1、0→2、2→1 会重复遇到 1，图却仍然无环。

Kahn 每次移除入度为 0 的节点。若队列清空后仍有节点，剩余每个节点都有前驱。在有限节点中沿前驱不断回走，必然重复，因此剩余子图存在环。

11.4 如何在线性时间判断二叉树是否高度平衡？

出现公司：暂无已核验的公开来源（本站自测）

考察重点：说明子树怎样同时返回高度与平衡结果，以及为什么能省去重复的高度计算。

相关内容：后序合并与树形结果。

参考回答

后序遍历让每棵子树返回高度或失败标记，就能在线性时间完成判断。

空子树返回 0。若任一子树返回 −1，或左右高度差大于 1，当前节点也返回 −1。否则，返回较大高度加 1，供父节点继续判断。

每个节点只合并一次，所以时间为 O(n)，递归空间为 O(h)。若对每个节点都重新计算两侧高度，链状树就会累计 O(n²) 的重复工作。

11.5 BFS 如何恢复一条最短路径？

出现公司：暂无已核验的公开来源（本站自测）

考察重点：解释首次发现时记录的前驱为何属于最短路径，并说明路径反转和不可达情况的处理。

相关内容：最短路径恢复。

参考回答

BFS 首次发现节点时记录前驱，就能在搜索结束后恢复一条最短路径。

单位边权下，首次发现来自最短距离层。目标可达时，沿 parent 从目标回走到源点，再反转顺序，就得到源点到目标的路线。源点 parent 可设为 −1，用作停止标记。目标 distance 仍为 −1 时，则返回无解。

11.6 二叉树最近公共祖先如何合并结果，目标缺失时怎么办？

出现公司：暂无已核验的公开来源（本站自测）

考察重点：按节点身份合并左右子树的搜索结果，并说明目标缺失为何需要额外验证。

相关内容：最近公共祖先。

参考回答

两个目标都存在时，可以合并左右子树的结果寻找最近公共祖先；目标允许缺失时，还需额外确认存在性。

空节点返回空，当前节点本身为目标时，直接作为候选返回。否则搜索两侧：若两侧各找到一个目标，当前节点就是最近公共祖先。只在一侧找到时，向上传递该侧结果。

若一个目标是另一个的祖先，上述过程会返回这个祖先。若目标可以缺失，只找到一个目标也会返回候选，所以还要验证两个目标都存在。判断时比较节点身份，避免把值相同的不同节点混在一起。

12. 参考资料

• Java SE 21：ArrayDeque
• Java SE 21：HashSet
• Java SE 21：PriorityQueue
• Princeton Algorithms：Directed Graphs
• Princeton Algorithms：BreadthFirstPaths 源码
• Java SE 21：JLS Record Classes
• Antti Laaksonen：Competitive Programmer’s Handbook