题目来源：改编自 LeetCode 108. 将有序数组转换为二叉搜索树。本 Lab 使用课程自定义输入输出协议和独立测试，不复制来源站点的代码或测试。
学习目标
前置知识与环境
先阅读第 8.1 节 基础查找与折半查找的"判定树与比较次数"一节，理解"取中点为根"得到的树形；再阅读第 8.2 节 二叉排序树的"BST 与折半查找的关系"一节，弄清有序表折半与平衡 BST 的对应。
在 Lab 目录执行 make doctor 检查环境；未安装 Make 时可在仓库根使用 pnpm 兜底命令（见下文"运行"）。
任务
给定一个严格递增的整数数组，把它转换成一棵平衡二叉搜索树，并输出该树的层序遍历。
原题的平衡 BST 答案不唯一，本 Lab 钉死如下确定性构造口径：递归处理闭区间 [l, r]，取左中点 mid = l + (r − l) / 2（即向下取整）作为根，先递归构造左子树，再递归构造右子树。左中点规则保证任意结点左右子树的结点数至多相差 1，树高为
输入格式
- 第一行：一个整数
n（可以为 0）； - 若
n > 0：第二行n个严格递增的整数。
输出格式
一行：构造出的平衡 BST 的层序遍历，从根开始逐层自左向右，同一行内用空格分隔；n = 0 时输出一个空行（空树）。
数据范围与限制
| 项目 | 范围 |
|---|---|
元素个数 n | 0 ≤ n ≤ 10⁴ |
| 元素取值 | |元素| ≤ 10⁹，严格递增 |
| 时间复杂度要求 | 递归建树与层序输出均为 |
| 输出上限 | 1 MB（一行 n ≤ 10⁴ 个整数，默认上限足够） |
正常、边界与错误情况
- 正常：奇数长度与偶数长度都按左中点取根，偶数长度取的是靠左的那个中点；
- 边界：
n = 0（空树，输出空行）；n = 1（根即唯一元素）；递归区间收缩到空区间（l > r）时返回空； - 口径提示：若改成"右中点"或"向上取整中点"，偶数长度的树形会不同——判题按本 Lab 的左中点口径逐个比对输出。
样例
样例 1
5
-10 -3 0 5 90 -10 5 -3 9[0, 4] 的左中点下标 2（值 0）为根；左子树 [0, 1] 取左中点下标 0（值 −10），它的右孩子是 [1, 1]（值 −3）；右子树 [3, 4] 取左中点下标 3（值 5），它的右孩子是 [4, 4]（值 9）。逐层输出：0；−10、5；−3、9。
样例 2
6
2 4 6 8 10 126 2 10 4 8 12[0, 5] 的左中点是下标 2（值 6）而不是下标 3——偶数长度取靠左的中点；左 [0, 1] 取下标 0（值 2），右孩子 4；右 [3, 5] 取下标 4（值 10），孩子 8 与 12。
实现提示
- 递归函数返回"子树根在结点数组中的下标"：用
vector保存结点（值 + 左右孩子下标），以push_back的先后次序获得新结点编号，避免递归中指针失效； - 层序遍历用队列：出队时先输出该结点值，再把非空的左、右孩子依次入队；
- 建树与遍历都是
n = 0时根为空，直接输出空行即可。
运行
make run
# 免 Make 兜底：在仓库根执行
pnpm lab:run -- labs/chapter-08/exercise/E-08-05-sorted-array-to-bst需要单用例或严格评分时使用 make run CASE=005-stress-1e4 与 make score；也可用 pnpm lab:score -- labs/chapter-08/exercise/E-08-05-sorted-array-to-bst 兜底。
完成清单
思考与复盘
- 把左中点改成右中点后，哪些
n的层序会改变？构造一个最小的反例。 - "先左后右"的递归顺序影响结点的创建次序；如果交换建树顺序，层序遍历的输出会变吗？为什么？
- 平衡 BST 的树高与折半查找判定树的高度有何关系？长度为 n 的表折半查找成功时最多比较多少次？