题目

题目来源：力扣（LeetCode）

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

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

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

思路分析

二叉搜索树的中序遍历结果是升序序列，题目给定的数组是按照升序排序的有序数组，因此可以确保数组是二叉搜索树的中序遍历序列。

我们可以以升序序列中的任意一个元素作为根节点，以该元素左边的升序序列构建左子树，以该元素右边的升序序列构建右子树，这样就可以得到一棵二叉搜索树。由于题目要求高度平衡，因此我们需要选择升序序列的中间元素作为根节点。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {number[]} nums
  11.  * @return {TreeNode}
  12.  */
  13. var sortedArrayToBST = function (nums) {
  14.   return dfs(nums, 0, nums.length - 1);
  16.   function dfs(nums, left, right) {
  17.     if (left > right) {
  18.       return null;
  19.     }
  20.     // 以升序数组的中间元素作为根节点 root，为了满足高度平衡
  21.     const mid = Math.floor((left+right)/2);
  22.     // const mid = (left + right) >> 1
  23.     const root = new TreeNode(nums[mid]);
  24.     // 递归的构建 root 的左子树与右子树。
  25.     // 以该元素左边的升序序列构建左子树，以该元素右边的升序序列构建右子树
  26.     root.left = dfs(nums, left, mid - 1);
  27.     root.right = dfs(nums, mid + 1, right);
  28.     return root;
  29.   }
  30. };

参考： https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/jian-dan-di-gui-bi-xu-miao-dong-by-sweetiee/