将有序数组转换为二叉搜索树
题目链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked
我的解答：
public TreeNode sortedArrayToBST(int[] nums) { int length = nums.length; if(length==0){ return null; } return createTree(nums,0,length-1); } public TreeNode createTree(int[] nums, int l, int r){ if(l>r){ return null; } int mid = (l+r)/2; TreeNode cur = new TreeNode(nums[mid]); cur.left = createTree(nums,l,mid-1); cur.right = createTree(nums,mid+1,r); return cur; }分析：代码的时间复杂度为O(n)，空间复杂度为O(logn)。解题思路：为了构建平衡搜索二叉树，每次取中间位置作为根节点，这样小于根节点的节点个数与大于根节点的节点个数之差不会大于1，即可以满足每个节点的左右子树的高度相差不超过1。
看了官方题解后的解答：
//方法一：中序遍历，总是选择中间位置左边的数字作为根节点 //int mid = (left + right) / 2; //方法二：中序遍历，总是选择中间位置右边的数字作为根节点 //int mid = (left + right + 1) / 2; //方法三：中序遍历，选择任意一个中间位置数字作为根节点 //int mid = (left + right + rand.nextInt(2)) / 2;分析：
1、官方题解的三种方法的解题思路差不多，都与我的解答思路一致，唯一的区别在于，[l,r]范围内的数据个数为偶数时，根节点有两种选择，而每次根节点的选择都会影响树的结构，故官方题解给出了三种方法，分别为每次选择中间位置左边的数字作为根节点、每次选择中间位置右边的数字作为根节点、随即选择中间位置的任意一边作为根节点。
2、三种方法的时间复杂度都为O(n)，空间复杂度都为O(logn)。
总结
- 本题主要需要知道“二叉搜索树的中序遍历是升序序列”，所以每次选取中间位置作为根节点，就可以保证左右子树的节点个数之差不超过1。
- 注意：根节点的选择策略的不同，会产生不同结构的但都符合题目要求的平衡二叉搜索树。
