- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
递归
- 二叉搜索树的中序遍历是升序的，本题中给出的数组刚好是升序的，相当于通过中序遍历恢复二叉搜索树
- 可以选择升序序列中的任意位置的元素作为根节点，该元素左边的升序序列构建左子树，右边的升序序列构建右子树
- 题目又要求高度平衡，所以我们需要选择升序序列的中间位置的元素作为根节点即可
constsortedArrayToBST=function(nums){constbuildTree=(Arr,left,right)=>{if(left>right)returnnullletmid=Math.floor(left+(right-left)/2)letroot=newTreeNode(Arr[mid])root.left=buildTree(Arr,left,mid-1)root.right=buildTree(Arr,mid+1,right)returnroot}returnbuildTree(nums,0,nums.length-1)}
- 时间复杂度：O(n)
- 空间复杂度：O(logn)