给你一个整数数组 nums，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树
高度平衡 二叉树是一棵满足 [每个节点的左右两个子树的高度差的绝对值不超过 1] 的二叉树

示例1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

分析

有序数组转二叉搜索树，需要以下几步：
1.找到中间位置
2.用中间位置的元素作为根节点
3.用中间位置左侧的元素构造左子树
4.用中间位置右侧的元素构造右子树

  1. public TreeNode sortedArrayToBST(int[] nums) {
  2.     // 找到中间位置索引
  3.     // 奇数个元素，则直接是中间位置元素
  4.     // 偶数个元素，则可以选择中间的左边一个元素
  5.     int midIndex = (0 + (nums.length - 1)) / 2;
  6.     // 从中间位置索引拆分数组
  7.     int[] leftArr = new int[midIndex];
  8.     int[] rightArr = new int[nums.length - 1 - midIndex];
  9.     for (int i = 0; i < midIndex; i++) {
  10.         leftArr[i] = nums[i];
  11.     }
  12.     for (int i = midIndex + 1, j = 0; i < nums.length; i++, j++) {
  13.         rightArr[j] = nums[i];
  14.     }
  15.     // 用中间索引位置的元素作为根节点
  16.     TreeNode root = new TreeNode(nums[midIndex]);
  17.     // 用左侧部分数组构造左子树
  18.     root.left = sortedArrayToBST(leftArr);
  19.     // 用右侧部分数组构造右子树
  20.     root.right = sortedArrayToBST(rightArr);
  21.     return root;
  22. }

完整递归算法

  1. public TreeNode sortedArrayToBST(int[] nums) {
  2.     // 递归结束条件
  3.     if (nums == null || nums.length == 0) {
  4.         return null;
  5.     }
  6.     // 找到中间位置索引
  7.     // 奇数个元素，则直接是中间位置元素
  8.     // 偶数个元素，则可以选择中间位置左边的元素
  9.     int midIndex = (0 + (nums.length - 1)) / 2;
  10.     // 从中间位置索引拆分数组
  11.     int[] leftArr = new int[midIndex];
  12.     int[] rightArr = new int[nums.length - 1 - midIndex];
  13.     for (int i = 0; i < midIndex; i++) {
  14.         leftArr[i] = nums[i];
  15.     }
  16.     for (int i = midIndex + 1, j = 0; i < nums.length; i++, j++) {
  17.         rightArr[j] = nums[i];
  18.     }
  19.     // 用中间索引位置的元素作为根节点
  20.     TreeNode root = new TreeNode(nums[midIndex]);
  21.     // 用左侧部分数组构造左子树
  22.     root.left = sortedArrayToBST(leftArr);
  23.     // 用右侧部分数组构造右子树
  24.     root.right = sortedArrayToBST(rightArr);
  25.     return root;
  26. }

递归算法优化分析

  1. 第一次计算：
  2. nums: [-10,-3,0,5,9]
  3. 中间索引：(0 + 5 - 1)/2 = 2 
  4. 构造左子树：左子树元素个数 2 ，需取 nums [0,1] 范围的元素
  5. 构造右子树：右子树元素个数 2 ，需取 nums [3,4] 范围的元素
  7. 第二次计算：
  8. arr1: [-10,-3]
  9. 中间索引：(0 + 2 -1)/2 = 0
  10. 构造左子树：左子树元素个数 0 
  11. 构造右子树：右子树元素个数 2，需取 arr1 [0,1] 范围的元素
  13. 第三次计算：
  14. arr2: [5,9]
  15. 中间索引：(0 + 2 -1)/2 = 0
  16. 构造左子树：左子树元素个数 0 
  17. 构造右子树：右子树元素个数 2，需取 arr2 [0,1] 范围的元素

arr1 [0,1] 范围的元素 实际等同于 nums [0,1] 范围的元素
arr2 [0,1] 范围的元素 实际等同于 nums [3,4] 范围的元素

那么是否可以每次都是从 nums 数组中直接取元素省略构造左侧数组和右侧数组的步骤？
每次可以指定一个左侧索引位置，一个右侧索引位置，每次都是在指定索引范围内从 nums 数组中取元素构建

  1. public TreeNode build(int[] arr, int left, int right) {
  2.     // 奇数个元素，则直接是中间位置元素
  3.     // 偶数个元素，则可以选择中间位置左边的元素
  4.     int midIndex = (left + right) / 2;
  5.     TreeNode root = new TreeNode(nums[midIndex]);
  6.     // 用左侧部分数组构造左子树
  7.     root.left = build(nums, left, midIndex - 1);
  8.     // 用右侧部分数组构造右子树
  9.     root.right = build(nums, midIndex + 1, right);
  10.     return root;
  11. }

优化后的递归算法

  1. public TreeNode sortedArrayToBST(int[] nums) {
  2.     return build(nums, 0, nums.length - 1);
  3. }
  4. private TreeNode build(int[] nums, int left, int right) {
  5.     if (left > right) {
  6.         return null;
  7.     }
  8.     // 奇数个元素，则直接是中间位置元素
  9.     // 偶数个元素，则可以选择中间位置左边的元素
  10.     int midIndex = (left + right) / 2;
  11.     TreeNode root = new TreeNode(nums[midIndex]);
  12.     // 用左侧部分数组构造左子树
  13.     root.left = build(nums, left, midIndex - 1);
  14.     // 用右侧部分数组构造右子树
  15.     root.right = build(nums, midIndex + 1, right);
  16.     return root;
  17. }

扩展

偶数个元素是否可以选择中间位置右边的元素？

  1. int midIndex = (left + right + 1) / 2;

偶数个元素是否可以随机取中间位置左边或者右边的元素？

  1. int midIndex = (left + right + rand.nextInt(2)) / 2;