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

力扣 108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
为什么平衡的二叉搜索树构建时需要选取有序数组的中间节点作为搜索树的根节点呢？可不可以从数组的第一元素作为根节点，以后按照搜索树和平衡树的准则构建呢？我下面的构造过程对不对呢？望朋友们为我指点迷津，谢谢啦！

图1、2是力扣官方给的答案，图a-g是我的构建过程。

使用第一个节点，就需要用到旋转，否则不平衡，从中间开始构建简单些

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7715516
• 以下回答来自chatgpt:

  在什么场景下你需要将有序数组转换为二叉搜索树？

  当我们需要对有序数组进行高效的查找、插入、删除等操作时，可以将有序数组转换为二叉搜索树，以便更方便地进行相关操作。

  你是否已经掌握了该题的基本解法？

  是的，基本解法是利用递归的方式，将有序数组的中间元素作为树的根节点，左边部分的数组构建左子树，右边部分的数组构建右子树，直到所有元素都被使用，并形成一棵高度平衡的二叉搜索树。

  你对于二叉搜索树和平衡树的理解如何？

  二叉搜索树本质是一棵二叉树，每个节点的值都大于等于其左子树所有节点的值，小于等于其右子树所有节点的值，且左右子树自身依然是二叉搜索树。

  平衡树是在二叉搜索树的基础上进行了优化，使得其插入、删除、查找等操作的时间复杂度均为O(logn)。AVL树和红黑树都是常见的平衡树。

  能否详细介绍一下构造过程？

  下面给出Java语言实现该题的递归代码，构造过程如下：

  1.首先需要选取有序数组的中间元素作为二叉搜索树的根节点（这里选取的是数组的中间位置）。

  2.然后，针对中间元素将数组分为两部分，左半部分构建成根节点的左子树，右半部分构建成根节点的右子树。

  3.接着，针对左子树，重复前两个步骤，继续递归地构建左子树的左子树和右子树，直到数组左半部分的元素全部被用完。

  4.针对右子树，同样递归地构建右子树的左子树和右子树，直到数组右半部分的元素全部被用完。

  5.最后，构建出来的二叉搜索树就是满足要求的，返回树的根节点即可。

  Java代码实现：

  public TreeNode sortedArrayToBST(int[] nums) { if(nums == null || nums.length == 0){ return null; } return buildTree(nums, 0, nums.length - 1); }

  private TreeNode buildTree(int[] nums, int left, int right){ if(left > right){ return null; } int mid = left + (right - left) / 2; TreeNode root = new TreeNode(nums[mid]); root.left = buildTree(nums, left, mid - 1); root.right = buildTree(nums, mid + 1, right); return root; }

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^