108. 将有序数组转换为二叉搜索树

题目描述

平衡二叉搜索树（Balanced Binary Search Tree）是一种特殊的二叉搜索树，它满足以下两个条件：

• 它是一棵二叉搜索树。意味着树中的任何节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值。
• 它是一棵平衡树。这意味着对于树中的任何节点，其左子树和右子树的高度差不超过 1。

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]

输出：[0,-3,9,-10,null,5]

解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案。

示例 2：

输入：nums = [1,3]

输出：[3,1]

解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

出处：LeetCode

解法一：递归

思路

递归遍历数组，每次取中间元素作为根节点，左右子树分别递归构建。

实现

function sortedArrayToBST(nums: number[]): TreeNode | null {
  const build = (left: number, right: number): TreeNode | null => {
    if (left > right) {
      return null;
    }
    const mid = left + Math.floor((right - left) / 2);
    const root = new TreeNode(nums[mid]);
    root.left = build(left, mid - 1);
    root.right = build(mid + 1, right);
    return root;
  };
  return build(0, nums.length - 1);
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(\log n)$

解法二：迭代

思路

使用栈模拟递归过程，每次取中间元素作为根节点，左右子树分别入栈。

实现

function sortedArrayToBST(nums: number[]): TreeNode | null {
  const root = new TreeNode(0);
  const stack = [[root, 0, nums.length - 1]];
  while (stack.length) {
    const [node, left, right] = stack.pop()!;
    const mid = left + Math.floor((right - left) / 2);
    node.val = nums[mid];
    if (left <= mid - 1) {
      node.left = new TreeNode(0);
      stack.push([node.left, left, mid - 1]);
    }
    if (mid + 1 <= right) {
      node.right = new TreeNode(0);
      stack.push([node.right, mid + 1, right]);
    }
  }
  return root;
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$