题目

对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是( )。

错因

B

凭直觉觉得"91 比 92 略小，紧接 20 又跳到 91，再到 34，看着上下乱跳"就排除。但 BST 路径允许这种"震荡"——只要每步都落在祖先节点夹出的合法区间内即可。逐步验证：92 → 20（左，区间 (−∞, 92)）→ 91 ∈ (20, 92) ✓ → 34 ∈ (20, 91) ✓ → 88 ∈ (34, 91) ✓ → 35 ∈ (34, 88) ✓，全部合法。

C

类似 B 的直觉错误："21 → 89 → 77 → 29 → 36 → 38" 看着抖动太大。验证：21 → 89（右，(21, +∞)）→ 77 ∈ (21, 89) ✓ → 29 ∈ (21, 77) ✓ → 36 ∈ (29, 77) ✓ → 38 ∈ (36, 77) ✓，合法。

D

类似的直觉问题。12 → 25 → 71 → 68 → 33 → 34：每步区间约束都满足（71 ∈ (12, +∞)、68 ∈ (25, 71)、33 ∈ (25, 68)、34 ∈ (33, 68)），是合法 BST 路径。

总解析

BST 查找路径的判定规则：把根节点初始范围视为 ，每走一步：

• 走左孩子 → 新范围为 （保持左下界，新右上界 = 当前值）
• 走右孩子 → 新范围为 （新左下界 = 当前值，保持右上界）

路径上每个节点必须落在前一步划出的合法区间内，否则该节点不可能存在于 BST 的对应位置。

逐项验证 A：95, 22, 91, 24, 94, 71

步	节点	当前合法区间	是否落入
1	95		✓
2	22	走左	✓
3	91	走右	✓
4	24	走左	✓
5	94	走右	✗ 94 > 91

第 5 步出现矛盾：91 是 24 的祖先（24 在 91 左子树），所以 24 后续路径上的所有节点必 < 91。但 94 > 91，违反约束——这样的 BST 在结构上不可能存在。

B、C、D 同法验证均合法（详见错因部分的逐步推导）。

最终答案是 A。