Easy

题目描述

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

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 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 <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 按 严格递增 顺序排列

解题思路

解题思路

这道题要求将有序数组转换为高度平衡的二叉搜索树。关键在于理解两个概念：

  1. 二叉搜索树性质：左子树所有节点值小于根节点，右子树所有节点值大于根节点
  2. 高度平衡：每个节点的左右子树高度差不超过1

由于数组已经有序，我们可以利用分治法来构建平衡BST：

核心思想：

  • 选择数组中间元素作为根节点，这样可以保证左右子树节点数量相差不超过1
  • 中间元素左侧的所有元素构成左子树
  • 中间元素右侧的所有元素构成右子树
  • 递归地对左右子数组应用相同策略

算法步骤：

  1. 如果数组为空，返回null
  2. 找到数组中间位置 mid = (left + right) / 2
  3. 创建根节点，值为 nums[mid]
  4. 递归构建左子树：使用 nums[left...mid-1]
  5. 递归构建右子树：使用 nums[mid+1...right]

这种方法确保了树的高度平衡性，因为每次都选择中间元素作为根，左右子树的规模相近。

推荐解法：分治递归法，时间复杂度最优且代码简洁。

代码实现

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return buildBST(nums, 0, nums.size() - 1);
    }
    
private:
    TreeNode* buildBST(vector<int>& nums, int left, int right) {
        if (left > right) return nullptr;
        
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        
        root->left = buildBST(nums, left, mid - 1);
        root->right = buildBST(nums, mid + 1, right);
        
        return root;
    }
};

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def buildBST(left, right):
            if left > right:
                return None
            
            mid = (left + right) // 2
            root = TreeNode(nums[mid])
            
            root.left = buildBST(left, mid - 1)
            root.right = buildBST(mid + 1, right)
            
            return root
        
        return buildBST(0, len(nums) - 1)

public class Solution {
    public TreeNode SortedArrayToBST(int[] nums) {
        return BuildBST(nums, 0, nums.Length - 1);
    }
    
    private TreeNode BuildBST(int[] nums, int left, int right) {
        if (left > right) return null;
        
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        
        root.left = BuildBST(nums, left, mid - 1);
        root.right = BuildBST(nums, mid + 1, right);
        
        return root;
    }
}

var sortedArrayToBST = function(nums) {
    function buildBST(left, right) {
        if (left > right) return null;
        
        const mid = Math.floor((left + right) / 2);
        const root = new TreeNode(nums[mid]);
        
        root.left = buildBST(left, mid - 1);
        root.right = buildBST(mid + 1, right);
        
        return root;
    }
    
    return buildBST(0, nums.length - 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分治递归法
时间复杂度O(n)
空间复杂度O(log n)

说明：

  • 时间复杂度：每个数组元素都会被访问一次来创建对应的树节点，所以是 O(n)
  • 空间复杂度：递归调用栈的深度等于树的高度，对于平衡BST高度为 O(log n)

相关题目