知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 04 - 将有序数组转换为二叉搜索树 ## 题目(LeetCode 108) 给你一个升序排列的整数数组 `nums`,将其转换为一棵高度平衡的二叉搜索树(BST)。 ``` 输入:nums = [-10,-3,0,5,9] 输出:[0,-3,9,-10,null,5] 0 / \ -3 9 / / -10 5 ``` ## 核心思路 有序数组的中间元素做根,天然保证左右子树节点数量接近(高度平衡)。 ``` nums = [-10, -3, 0, 5, 9] 1. 中间元素 nums[2] = 0 → 根 2. 左半 [-10, -3] → 递归构造左子树 3. 右半 [5, 9] → 递归构造右子树 左半 [-10, -3]: 中间 nums[0] = -10(或 nums[1] = -3,取决于偏左还是偏右) 这里取 mid = (0+1)/2 = 0 → -10 做根,右子 -3 右半 [5, 9]: 中间 nums[3] = 5(或 9) 这里取 mid = (3+4)/2 = 3 → 5 做根,右子 9 ``` ## 代码 ```java class Solution { public TreeNode sortedArrayToBST(int[] nums) { return build(nums, 0, nums.length - 1); } private TreeNode build(int[] nums, int lo, int hi) { if (lo > hi) return null; int mid = lo + (hi - lo) / 2; // 取中间元素做根 TreeNode root = new TreeNode(nums[mid]); root.left = build(nums, lo, mid - 1); root.right = build(nums, mid + 1, hi); return root; } } ``` ## 为什么取中间元素就能保证平衡? ``` 数组长度 n,取中间做根: 左子树节点数 ≈ n/2 右子树节点数 ≈ n/2 → 高度差最多 1 → 平衡 如果取第一个元素做根: 左子树 0 个节点,右子树 n-1 个节点 → 退化成链表 → 不平衡 ``` 这和二分查找的思想完全一样:每次取中间,把问题规模减半。 ## 复杂度 - 时间 O(n):每个元素处理一次 - 空间 O(log n):递归栈深度(平衡树高度) --- 上一篇:[03 - 最大二叉树](./03-maximum-binary-tree.md) | 下一篇:[05 - 有序链表转换为 BST](./05-sorted-list-to-bst.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入