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

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

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

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

【考点】二叉搜索树遍历特性｜树形结构约束｜深度与父子关系判定

1. 🎯 考纲定位：GESP C++ 六级 数据结构模块，二叉搜索树遍历特性与树形结构约束。命题人卡住考生"先序定根、中序定左右子树范围"这一核心建模步骤，多数学生只背遍历顺序却不会逆向还原树形，这类题在六级中常作为区分度考点，尤其考察对BST性质的深层理解。

2. 🧠 解题思维：先序首元3即为根，中序{1,2,3,4,5}确定左子树含{1,2}、右子树含{4,5}。右子树两节点在BST中必为父子（较大者只能在其父的右子树），故4与5绝不可能是兄弟。通法：由先序定根、由中序定左右子树元素集合，再结合BST性质判断节点间父子/兄弟关系，此法可迁移至任意BST遍历还原题，是六级高频考点。

3. 🪤 陷阱拆解：A错在混淆"完全二叉树"定义；C错在忽略左子树仅2个节点，根深度1，左子树根深度2，1所在节点深度≤2；D错在误判1与2的父子关系（1可为左子树根，2为其右孩子，2的父亲是3）。命题人利用学生对"深度"与"父子"概念的模糊理解设陷阱，尤其C选项的"可能大于3"看似宽泛实则绝对化，易诱导考生误判，需严格计算节点深度。

4. 🔄 反命题思维：若先序改为{3,4,5,1,2}，则根仍为3，但右子树{4,5}先于左子树{1,2}，4与5仍为父子；若中序改为{1,3,2,4,5}，树形结构将完全不同，4与5可能成为兄弟。刷到此类题时先自问"遍历顺序如何影响节点位置"，再结合BST性质验证选项，避免盲目代入，这是六级命题的常用手法。