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

题目描述

题解(前序遍历)

• 输入的升序数组 = 目标树的中序遍历结果。
• 代码的实际执行 = 构造二叉树的前序遍历过程。

思路

代码

classSolution{publicTreeNodesortedArrayToBST(int[]nums){// 调用辅助函数，传入数组的左右边界returnbuildTree(nums,0,nums.length-1);}// 辅助函数：根据指定的左右边界构建平衡二叉搜索树privateTreeNodebuildTree(int[]nums,intleft,intright){// 1. 递归终止条件：当左边界大于右边界时，说明区间内没有元素了，返回 nullif(left>right){returnnull;}// 2. 找到当前区间的中间位置（防溢出写法）// 如果区间长度为偶数，这里总是选择中间靠左的元素作为根节点intmid=left+(right-left)/2;// 3. 构造当前的根节点TreeNoderoot=newTreeNode(nums[mid]);// 4. 递归构造左子树（范围是 left 到 mid - 1）root.left=buildTree(nums,left,mid-1);// 5. 递归构造右子树（范围是 mid + 1 到 right）root.right=buildTree(nums,mid+1,right);// 6. 返回构造好的根节点returnroot;}}

复杂度分析

• 时间复杂度: O(N)，其中 N 是数组的长度。我们需要遍历数组中的每一个元素来创建一个对应的树节点，每个元素只被访问一次。
• 空间复杂度主要取决于递归调用栈的深度。因为我们每次都选择中间元素作为根节点，所以构建出来的是一棵高度平衡的二叉树，其高度始终保持在 O(log N) 级别。