GESP 七级 · GESP 202406 C++ 七级 第 15 题

下列选项中，哪个可能是下图的深度优先遍历序列（ ）。


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

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

【考点】深度优先遍历｜二叉树结构

【考纲定位】GESP 七级《算法与程序设计》模块核心考点。命题人专门选这道题，就是要卡住那些只会背"前序/中序/后序"口诀、从不验证树结构的学生——他们一看到 DFS 就条件反射选第一个看起来顺眼的，完全没管节点间的父子关系。

【解题思维】DFS 遍历二叉树有铁律：父节点必在所有子节点之前访问。拿到序列后，把每个数当根节点，看它右边的数能不能构成合法左子树和右子树。A 选项 3 出现在 1 之后，但 3 的右子树里 7 又比 3 晚，说明 3 不是根，矛盾；B 选项 1 在最中间，它左边的 9,4,2 左子树里 4 的右子树 3 却比 1 晚，1 成了 3 的祖先却后访问，死；C 选项 1 为根，左子树 3-2-7-6-8，右子树 4-9-5，所有子节点都紧跟在父节点之后，完美符合；D 选项 9 为根，左子树 7-6-8-4-2，但 1 作为 2 的祖先却比 2 晚，不可能。只有 C 满足二叉树 DFS 的父子先后约束。

【陷阱拆解】A 选项偷换父子关系——让子节点 3 比父节点 1 早访问；B 选项把根节点 1 插在中间，子树左右顺序完全错乱；D 选项更是离谱，9 为根却把 1 赶到后面。最阴险的是命题人没给图，让你凭序列反推树结构——如果你只记得"根左右"口诀，一看到 1,3,4...就下意识选 C，其实 C 的右子树 4-9-5 里 9 是左子节点，这顺序在标准 DFS 里根本不可能出现。记住：DFS 序列不仅要看先后，还要看左右分支是否闭合。

【反命题思维】这题如果改成"以下哪个不可能是 DFS 序列"，正确答案就会变成 A 或 B；要是加个条件"假设采用右子树优先的 DFS"，C 就会立刻失效。刷题遇到这类题先问自己：这个节点真的是它上面那个节点的直接子节点吗？