手帐 Blog

主题

复盘 · LC 108 将有序数组转换为二叉搜索树 ​

题目 ​

题意 ​

升序数组转成一棵高度平衡的 BST（任意节点左右子树高度差 ≤ 1）。答案不唯一，满足平衡 + BST 即可。

  • 空数组 → null。
  • 中序遍历应还原为原数组顺序。

涉及算法 ​

标签一句话
分治 / 二分取中中点做根 → 左半建左子树、右半建右子树，天然平衡且满足 BST
BST有序序列的中序即 BST 的中序

教程对照：18 · BFS 层序与 BST、14 · 二分查找标准模板（取 mid 手感）。

评价我的解法 ​

区间递归取 mid，写法标准。

我的代码（摘自 108-将有序数组转换为二叉搜索树/index.js，不含本地测例）：

javascript
var sortedArrayToBST = function (nums) {
  function createTree(left, right) {
    if (left > right) {
      return null;
    }
    const mid = Math.floor((left + right) / 2);
    const node = new TreeNode(nums[mid]);
    node.left = createTree(left, mid - 1);
    node.right = createTree(mid + 1, right);
    return node;
  }
  const res = createTree(0, nums.length - 1);
  return res;
};

评价：

  1. 正确且干净：left > right 终止；mid 做根；左右闭区间切开——就是题解模板。
  2. 平衡性：每次取中点，子树规模近似对半，高度 O(log n)。
  3. 小瑕疵：const res = ...; return res 可直接 return createTree(...)；TreeNode 本地重复定义不影响提交版。
  4. 复杂度：时间 O(n)（每元素建一次），空间 O(log n) 递归栈（不计输出树）。

小结：BST + 有序数组这题一次到位，说明分治取中已经形成肌肉记忆。

最佳题解 ​

与你同构：

javascript
/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function (nums) {
  function build(l, r) {
    if (l > r) return null;
    const mid = (l + r) >> 1;
    const node = new TreeNode(nums[mid]);
    node.left = build(l, mid - 1);
    node.right = build(mid + 1, r);
    return node;
  }
  return build(0, nums.length - 1);
};
  • 时间 O(n)，空间 O(log n) 栈。
  • 选左中位或右中位（mid = (l + r + 1) >> 1）都合法，只影响形状，不影响「平衡 BST」判定。

关联题目 ​

题为何相关
109. 有序链表转换二叉搜索树同题链表版；快慢找中点
98. 验证二叉搜索树BST 性质反向检验
95. 不同的二叉搜索树 II枚举根的分治建树

一句话带走 ​

有序数组建平衡 BST：每次取中点当根，左右递归——中序还原即原数组。