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

将有序数组转换为二叉搜索树题目链接https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public TreeNode sortedArrayToBST(int[] nums) { int length nums.length; if(length0){ return null; } return createTree(nums,0,length-1); } public TreeNode createTree(int[] nums, int l, int r){ if(lr){ return null; } int mid (lr)/2; TreeNode cur new TreeNode(nums[mid]); cur.left createTree(nums,l,mid-1); cur.right createTree(nums,mid1,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。注意根节点的选择策略的不同会产生不同结构的但都符合题目要求的平衡二叉搜索树。