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

Categories:

Tags:

题目描述
思路分析
1. 解法一：分治递归（推荐）
相似题目

题目描述

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

思路分析

解法一：分治递归（推荐）

核心思路：

高度平衡的 BST 要求每个节点的左右子树高度差不超过 1，因此每次取数组的中间元素作为根节点，可以保证左右子树节点数量均衡。

递归地对左半部分数组构建左子树，对右半部分数组构建右子树。

当区间为空（left > right）时，返回 nil/null，作为递归终止条件。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度，每个元素恰好被访问一次。

空间复杂度：O(log n)，其中 log n 表示递归调用栈的深度，即平衡 BST 的高度。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    private TreeNode build(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 = build(nums, left, mid - 1);
        // 递归构建右子树
        root.right = build(nums, mid + 1, right);
        return root;
    }
}

func sortedArrayToBST(nums []int) *TreeNode {
    var build func(left, right int) *TreeNode
    build = func(left, right int) *TreeNode {
        // 区间为空时递归终止
        if left > right {
            return nil
        }
        // 取中间元素作为当前子树的根节点，保证左右子树节点数均衡
        mid := left + (right-left)/2
        root := &TreeNode{Val: nums[mid]}
        // 递归构建左子树
        root.Left = build(left, mid-1)
        // 递归构建右子树
        root.Right = build(mid+1, right)
        return root
    }
    return build(0, len(nums)-1)
}

相似题目

题目	难度	考察点
109. 有序链表转换二叉搜索树	中等	分治、递归、二叉搜索树构造
1008. 从前序遍历重建二叉搜索树	中等	分治、递归、二叉搜索树构造
105. 从前序与中序遍历序列构造二叉树	中等	分治、递归、二叉树构造
106. 从中序与后序遍历序列构造二叉树	中等	分治、递归、二叉树构造
889. 根据前序和后序遍历构造二叉树	中等	分治、递归、二叉树构造
654. 最大二叉树	中等	分治、递归、二叉树构造

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/80396602