给你一个整数数组 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,3] 和 [3,1] 都是高度平衡二叉搜索树。

题解

根据二叉搜索树的性质，可以采用分治法来构建。

取有序列表的中位数来作为节点的值， nums = [-10,-3,0,5,9] 取 0 作为节点

剩下的数字再分为 [-10,-3] [5,9] 递归构建左右子树

但列表没有数字时，表明不需要节点，返回 null

  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) {
  15.     const run = (list) => {
  16.         if (list.length === 0) {
  17.             return null
  18.         }
  19.         const mid = Math.floor(list.length / 2)
  20.         const node = new TreeNode(list[mid])
  22.         const left  = list.slice(0, mid)
  23.         const right = list.slice(mid + 1, list.length)
  25.         node.left = run(left)
  26.         node.right = run(right)
  28.         return node
  29.     }
  30.     return run(nums)
  31. };

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。