题目描述

给定一个有序数组（升序排列），要求将这个有序数组转换成一棵高度平衡的二叉搜索树（BST）。在二叉搜索树中，对于树中的每个节点X，其左子树中的所有项的值都小于X中的项，而其右子树中的所有项的值都大于X中的项。高度平衡的二叉搜索树是指一个二叉树，其中每个节点的两个子树的高度差的绝对值不超过1。

示例

假设给定的有序数组为 [-10, -3, 0, 5, 9]，一个可能的平衡二叉搜索树如下（这不是唯一解）：

    0
   / \
 -3   5
 /   / \
-10   9

解题思路

为了构建一棵平衡的二叉搜索树，我们可以选择数组的中间元素作为根节点。这样，根节点的左侧子数组中的所有元素都小于根节点的值，而右侧子数组中的所有元素都大于根节点的值。然后，我们可以递归地对左子数组和右子数组执行相同的操作，以构建左子树和右子树。

PHP 示例代码

class TreeNode {
    public $val;
    public $left;
    public $right;
    
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

function sortedArrayToBST($nums) {
    if (empty($nums)) {
        return null;
    }
    
    $mid = intdiv(count($nums), 2);
    $root = new TreeNode($nums[$mid]);
    $root->left = sortedArrayToBST(array_slice($nums, 0, $mid));
    $root->right = sortedArrayToBST(array_slice($nums, $mid + 1));
    
    return $root;
}

Python 示例代码

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sortedArrayToBST(nums):
    if not nums:
        return None
    
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums[:mid])
    root.right = sortedArrayToBST(nums[mid+1:])
    
    return root

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) {
        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;
}

这些示例代码展示了如何将一个有序数组转换为一棵高度平衡的二叉搜索树。在码小课网站上，你可以进一步学习关于二叉搜索树和其他数据结构的更多内容。