GESP 六级 · GESP 202603 C++ 六级 第 13 题

下列关于树的深度优先搜索（DFS）的说法中，正确的是（ ）。

DFS 使用栈（或递归），沿一条路径走到底再回溯，适合遍历所有可能状态。注意回溯时的状态恢复。

DFS 递归遍历时注意状态回溯（恢复现场）。图遍历需要visited数组避免重复访问和死循环。

【考点】深度优先搜索｜递归与栈｜树遍历特性

🎯 考纲定位 本题考查《GESP C++ 六级》考察图与树遍历的核心概念。命题人卡住的是混淆 DFS 与 BFS 层序遍历、误认为遍历序列唯一或仅限二叉树的认知盲区。

🧠 解题思维 看到 DFS 先想：深度优先意味着沿一条路径走到底再回溯，必然用递归或栈模拟。遍历顺序取决于子节点访问次序，对普通树同样适用。递归天然处理树结构，栈是显式替代方案。

🪤 陷阱拆解 选项 A 偷换概念：从上到下是 BFS 层序，DFS 会先深入子节点；选项 B 绝对化：DFS 序列依赖子节点访问顺序，左右交换就不同；选项 D 范围错误：DFS 是通用图遍历算法，完全适用于普通树。只有 C 精准描述实现手段。

🔄 反命题思维 命题人想考你是否区分遍历算法与数据结构限制。若改成「对图进行 DFS，得到的访问序列唯一」，答案会否？若限定为「二叉树 DFS 序列唯一」，结论仍不成立。刷到类似题先问：题目在限制算法应用范围还是考察实现机制？