有序数组转换为平衡二叉搜索树（BST）的算法实现

将有序数组转换为二叉搜索树（BST）是一个常见的算法问题。二叉搜索树是一种特殊的二叉树，其中每个节点的左子树包含的值都小于该节点的值，而右子树包含的值都大于该节点的值。由于数组是有序的，我们可以利用二分查找的思想来构建平衡的二叉搜索树。

实现思路

1. 选择中间元素作为根节点：为了保持树的平衡，我们选择数组的中间元素作为根节点。
2. 递归构建左子树和右子树：对数组的左半部分递归构建左子树，对数组的右半部分递归构建右子树。

代码实现

以下是使用 JavaScript 实现的代码：

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val);
    this.left = (left === undefined ? null : left);
    this.right = (right === undefined ? null : right);
}

function sortedArrayToBST(nums) {
    if (nums.length === 0) return null;

    // 找到中间元素的索引
    const mid = Math.floor(nums.length / 2);

    // 创建根节点
    const root = new TreeNode(nums[mid]);

    // 递归构建左子树和右子树
    root.left = sortedArrayToBST(nums.slice(0, mid));
    root.right = sortedArrayToBST(nums.slice(mid + 1));

    return root;
}

// 示例用法
const nums = [-10, -3, 0, 5, 9];
const bst = sortedArrayToBST(nums);

console.log(bst);

代码解释

1. TreeNode 类：定义了一个简单的二叉树节点类，包含 val、left 和 right 属性。
2. sortedArrayToBST 函数：
   • 如果数组为空，返回 null。
   • 找到数组的中间元素，并将其作为根节点。
   • 递归地对数组的左半部分和右半部分调用 sortedArrayToBST，分别构建左子树和右子树。
   • 返回构建好的二叉搜索树的根节点。

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。每个元素都会被访问一次。
• 空间复杂度：O(log n)，递归栈的深度为树的高度，由于树是平衡的，高度为 log n。

总结

通过选择中间元素作为根节点并递归构建左右子树，我们可以高效地将有序数组转换为平衡的二叉搜索树。这种方法不仅简单，而且保证了树的平衡性，使得树的操作（如查找、插入、删除）都能在 O(log n) 的时间内完成。