hot100 将有序数组转换为二叉搜索树(108)

本题采用二分分治递归算法又称“中点根节点映射法”解决将有序数组转换为高度平衡二叉搜索树的问题。其核心本质是将一维有序区间的几何中心元素抽象为二叉树的局部根节点通过等分剩余区间确保左右子树的规模差异不超过 1。当前提供的源码实现了在时间复杂度 O(n) 和额外空间复杂度 O(log n) 条件下的全局最优平衡重构最终走向是精准输出一棵满足二叉搜索树及高度平衡双重约束的平衡二叉树。一、 问题本质与数据模型对于严格递增的整数数组 nums题目要求构建一棵平衡二叉搜索树BST。该问题面临两个核心物理约束二叉搜索树约束左子树所有节点值小于根节点值右子树所有节点值大于根节点值。高度平衡约束任意节点的左右子树高度差绝对值不超过 1。由于输入的数组已经按升序排列数组本身就是二叉搜索树中序遍历的线性展现。若从数组的任意一端如最左侧或最右侧开始作为根节点盲目构建将导致树向单侧极端倾斜退化为线性链表从而破坏高度平衡。为了破除这种拓扑非对称困局算法引入了“中点分割模型”。每次选择当前子数组区间的几何中心mid left (right - left) / 2作为局部根节点。由于数组有序该元素左侧的所有元素必然小于它右侧的所有元素必然大于它天然满足二叉搜索树属性同时左右两侧的剩余元素数量差至多为 1确保了自底向上回溯时左右子树的高度差绝对值不超过 1从而在几何上强制实现树的全局高度平衡。二、 算法演进对比在将有序序列转化为平衡 BST 的场景中中点分治法在时空资源的控制上达到了平衡极限解法名称时间复杂度空间复杂度核心原理物理瓶颈 / 缺陷逐个节点插入法O(n 阶平方)O(1)遍历有序数组对每个元素调用常规 BST 插入操作由于元素有序常规插入会导致树退化为单链表效率低下且破坏平衡性中点分治法当前解法O(n)O(log n)每次选取区间中点作为根等分左右区间并行递归依赖数组的随机访问特性若输入数据结构退化为单链表则无法直接定位中点中序遍历模拟法O(n)O(log n)建立全局计数器配合中序遍历顺序依序构建节点并装配编码逻辑较为抽象需要精确维护全局指针与树结构的物理状态同步三、 核心分支控制逻辑与决策证明当前源码的控制流完全依赖于私有递归函数dfs(nums, left, right)内的区间边界判定与节点组装其内部决策分支证明如下1. 越界空值分支if (left right)执行直接返回 null。物理意义当左边界指针大于右边界指针时说明当前子区间已经不包含任何物理元素。该子树属于虚拟空边界返回 null 作为叶子节点的终止标识。2. 中点值物理映射int mid left (right - left) / 2;执行计算中点索引并构造TreeNode root new TreeNode(nums[mid]);数学证明使用防溢出公式确定当前有效区间的中心位置。由于数组严格升序nums[mid]将当前区间切分为[left, mid - 1]和[mid 1, right]两个子弹道。左侧子数组所有值均小于nums[mid]右侧均大于nums[mid]此映射完全符合二叉搜索树的物理定义。3. 左子树递归分支root.left dfs(nums, left, mid - 1);执行将左侧剩余子区间作为左子树的数据域进行递归构建。数学证明左侧子区间的规模为(mid - 1) - left 1其内部元素继续遵循相同的等分策略确保生成的左子树高度均匀。4. 右子树递归分支root.right dfs(nums, mid 1, right);执行将右侧剩余子区间作为右子树的数据域进行递归构建。数学证明右侧子区间的规模为right - (mid 1) 1。左右两个子区间的元素个数之差绝对值小于或等于 1从而在数学上证明了左右子树高度差绝对值不大于 1。四、 算法执行状态机步进示例以输入有序数组nums [-10, -3, 0, 5, 9]为例规模 n 5预期树高 h 3递归调用栈的步进与状态机上演进过程如下表所示注区间用标准闭区间表示步骤当前递归区间 [left, right]计算所得中点 mid (对应数值)触发的分支与状态判定空间调用栈物理状态说明初始[0, 4]2 (数值: 0)选取 0 为全局根节点触发左区间 [0, 1] 递归栈深: [ [0,4] ]1[0, 1]0 (数值: -10)选取 -10 为局部根触发左区间 [0, -1] 递归栈深: [ [0,4], [0,1] ]2[0, -1]越界满足 left 大于 right直接返回 null栈深: [ [0,4], [0,1], [0,-1] ] - 弹出3[0, 1]0 (数值: -10)左孩子挂载 null触发右区间 [1, 1] 递归栈深: [ [0,4], [0,1] ]4[1, 1]1 (数值: -3)选取 -3 为叶子节点其左右子区间均越界返回 null栈深: [ [0,4], [0,1], [1,1] ] - 弹出5[0, 1]0 (数值: -10)右孩子挂载 -3当前子树构建完成向上传递节点 -10栈深: [ [0,4], [0,1] ] - 弹出6[0, 4]2 (数值: 0)根节点 0 挂载左孩子 -10触发右区间 [3, 4] 递归栈深: [ [0,4] ]7[3, 4]3 (数值: 5)选取 5 为局部根触发左区间 [3, 2] 返回 null触发右区间 [4, 4]栈深: [ [0,4], [3,4] ]8[4, 4]4 (数值: 9)选取 9 为叶子节点其左右均返回 null返回节点 9栈深: [ [0,4], [3,4], [4,4] ] - 弹出9[3, 4]3 (数值: 5)右孩子挂载 9当前子树构建完成向上传递节点 5栈深: [ [0,4], [3,4] ] - 弹出10[0, 4]2 (数值: 0)根节点 0 挂载右孩子 5全局构建完成返回最终根节点栈深: [ [0,4] ] - 弹出流程结束五、 源码实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public TreeNode sortedArrayToBST(int[] nums) { // 启动分治深度优先搜索初始化边界为数组的完整物理区间 return dfs(nums, 0, nums.length - 1); } private TreeNode dfs(int[] nums, int left, int right) { // 基准收敛条件若左边界超越右边界说明当前区间为空无法构成节点 if (left right) { return null; } // 核心控制计算区间的几何中心点采用防加法溢出结构 int mid left (right - left) / 2; // 物理映射以中点元素的值实例化当前子树 the 根节点 TreeNode root new TreeNode(nums[mid]); // 分治递归将中点左侧的升序子区间递归构建为当前根节点的左子树 root.left dfs(nums, left, mid - 1); // 分治递归将中点右侧的升序子区间递归构建为当前根节点的右子树 root.right dfs(nums, mid 1, right); // 状态回溯返回已经装配好左右子树的局部平衡 BST 根节点 return root; } }六、 复杂度分析1. 时间复杂度O(n)分析算法通过二分法将一维数组逐步切分。在整个分治递归过程中数组中的每一个元素都被选定且仅选定为一次中点即被实例化为一个独立的二叉树节点。在每个节点上的局部操作算术中点求值、指针赋值、局部新建节点消耗均为常数阶时间 O(1)。如果有 n 个元素整体计算步数与元素总量 n 呈严格的线性正比关系。结论时间复杂度为 O(n)达到了所有二叉树线性重构算法的理论上限。2. 空间复杂度O(log n)分析算法在运行期间未使用任何与输入规模成正比的外部独立数据结构如额外的数组或队列。由于算法采用严格的二分法进行递归区间切分递归调用栈的深度取决于二叉树的高度。在每次对半分的策略下构建出的二叉树是一棵完全平衡二叉树其高度严格被限制在 log n 级别。结论最大系统栈内存空间开销恒定在对数阶 O(log n)。