1. 题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:
给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

  1.       0
  2.      / \
  3.    -3   9
  4.    /   /
  5.  -10  5

2. 解题思路

题目要求是将数组的值转化为一个高度平衡的二叉搜索树，我们只要找到中间的元素作为根节点，然后将中间元素的左边和右边分别二分，找出中间值作为子树的根节点，重复上述操作，直到遍历完整个数组为止即可。

  • 当数组长度为奇数时，以中间值作为根节点，形成的平衡二叉搜索树的两侧差值为0
  • 当数组长度为偶数时，可以取中间两个元素的任意一个作为根节点的值，这样形成的平衡二叉树的两侧差值的绝对值为1

这里使用到了floor()方法：

  • floor() 方法返回小于等于x的最大整数
  • 如果传递的参数是一个整数，该值不变

    3. 代码实现

    1. /**
    2. * Definition for a binary tree node.
    3. * function TreeNode(val) {
    4. *     this.val = val;
    5. *     this.left = this.right = null;
    6. * }
    7. */
    8. /**
    9. * @param {number[]} nums
    10. * @return {TreeNode}
    11. */
    12. var sortedArrayToBST = function(nums) {
    13.  if(!nums.length){
    14.      return null
    15.  }
    16.  function bst(low, high){
    17.      // 遍历结束条件
    18.      if(low>high){
    19.          return null
    20.      }
    21.      // 取出当前子序列的中间元素的索引值
    22.      const mid = Math.floor(low+(high-low)/2)
    23.      // 将中间元素的值作为当前子树的根节点
    24.      const cur = new TreeNode(nums[mid])
    25.      // 递归构建左子树
    26.      cur.left = bst(low, mid-1)
    27.      // 递归构建右子树
    28.      cur.right = bst(mid+1, high)
    29.      return cur
    30.  }
    31.  return bst(0, nums.length-1)
    32. };

    4. 提交结果

    108. 将有序数组转换为二叉搜索树 - 图1