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

题目描述题解(前序遍历)输入的升序数组 目标树的中序遍历结果。代码的实际执行 构造二叉树的前序遍历过程。思路代码classSolution{publicTreeNodesortedArrayToBST(int[]nums){// 调用辅助函数传入数组的左右边界returnbuildTree(nums,0,nums.length-1);}// 辅助函数根据指定的左右边界构建平衡二叉搜索树privateTreeNodebuildTree(int[]nums,intleft,intright){// 1. 递归终止条件当左边界大于右边界时说明区间内没有元素了返回 nullif(leftright){returnnull;}// 2. 找到当前区间的中间位置防溢出写法// 如果区间长度为偶数这里总是选择中间靠左的元素作为根节点intmidleft(right-left)/2;// 3. 构造当前的根节点TreeNoderootnewTreeNode(nums[mid]);// 4. 递归构造左子树范围是 left 到 mid - 1root.leftbuildTree(nums,left,mid-1);// 5. 递归构造右子树范围是 mid 1 到 rightroot.rightbuildTree(nums,mid1,right);// 6. 返回构造好的根节点returnroot;}}复杂度分析时间复杂度: O(N)其中 N 是数组的长度。我们需要遍历数组中的每一个元素来创建一个对应的树节点每个元素只被访问一次。空间复杂度主要取决于递归调用栈的深度。因为我们每次都选择中间元素作为根节点所以构建出来的是一棵高度平衡的二叉树其高度始终保持在 O(log N) 级别。