CSP-S 2025 第一轮 第8题：如果一棵二叉搜索树的后序遍历序列是 2, 5, 4, 8, 12, 10, 6，

题目

如果一棵二叉搜索树的后序遍历序列是 $2, 5, 4, 8, 12, 10, 6$，那么该树的前序遍历是什么？

选项

• A. $6, 4, 2, 5, 10, 8, 12$
• B. $6, 4, 5, 2, 10, 12, 8$
• C. $2, 4, 5, 6, 8, 10, 12$
• D. $12, 8, 10, 5, 2, 4, 6$

答案

A

题解

答案是 A：\(6, 4, 2, 5, 10, 8, 12\)。

用到两个规则：

• 后序遍历顺序是“左子树 → 右子树 → 根”，所以最后一个数 \(6\) 是根。
• 二叉搜索树的左子树所有值小于根，右子树所有值大于根。

因此，去掉根 \(6\) 后，序列分成：

\[ \underbrace{2,5,4}_{\text{左子树，小于 }6},\quad \underbrace{8,12,10}_{\text{右子树，大于 }6} \]

继续按同样方法拆分：

• 左子树的根是末尾的 \(4\)，左孩子为 \(2\)，右孩子为 \(5\)。
• 右子树的根是末尾的 \(10\)，左孩子为 \(8\)，右孩子为 \(12\)。

得到这棵树：

``text 6 / \ 4 10 / \ / \ 2 5 8 12 ``

前序遍历按“根 → 左子树 → 右子树”，所以结果是：

\[ \boxed{6,4,2,5,10,8,12} \]