GESP 八级 · GESP 202603 C++ 八级 第 5 题

在二叉搜索树（BST）中，若中序遍历的序列为 $\{1, 2, 3, 4, 5\}$，且先序遍历的第一个序列元素为 $3$，则下列说法正确的是（ ）。

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

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

【考点】二叉搜索树构造｜中序/先序遍历性质｜判定树结构与深度

考纲定位：GESP 八级树结构考点，命题人用"已知中序 + 先序首元"反推 BST 唯一形态，专卡考生对遍历序列与树形对应关系的盲区。

解题思维：先序首元 3 必为根，中序{1,2}在左{4,5}在右；左子树中序首元 1 为左孩子、2 为右孩子，右子树中序首元 4 为右孩子、5 为右孩子，还原为 3→(1→2, 4→5) 的右斜树。

陷阱拆解：A 错在把"非完全"当"一定完全"；B 对——4 与 5 是爷孙关系而非兄弟；C 错在把深度 2 偷换成"可能大于 3"；D 错在把父子方向颠倒。命题人用"一定""可能"等绝对化词制造语义陷阱，只背结论不看结构必踩。

反命题思维：若把先序首元改为 1，则根变 1，中序划分后 2 成为右孩子，树形完全反转，B 选项将变为假。刷到类似题先问"根是谁、左右子树边界在哪"，就能避开被选项牵着走的坑。