GESP 七级 · GESP 202512 C++ 七级 第 14 题

下面哪一个可能是下图的深度优先遍历序列（ ）。


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

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

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

DFS 从根开始：1 被访问。接着进入 1 的左子树，5 被访问。5 的左子树 8 被访问，8 的左子树 9 被访问，9 的左子树 7 被访问，7 的左子树 4 被访问，4 的左子树 6 被访问，6 的左子树 3 被访问，3 的左子树 2 被访问。所有子树访问完后返回根 1，序列为 1,5,8,9,7,4,6,3,2，与 B 完全一致。

陷阱拆解：A 错在把 5 的左子树 8 和 9 提前了，DFS 必须先走完 5 的所有后代；C 和 D 直接以 3 或 2 开头，显然不是根节点，违反"先访问根"的规则。

反命题思维：若把树中 5 和 3 的位置互换，正确答案就会变成 A。刷到类似题时，先问自己"这棵树根是谁？它的子树顺序是什么？"——这才是 DFS 题的命门。