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

题目

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

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

示例:

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

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

​ 0 ​ / ​ -3 9 ​ / / -10 5

解答

递归

既然已经有了顺序，那么可以从中间开始，左一个右一个地递归插入二叉树。

var sortedArrayToBST = function (nums) {
  if (nums.length === 0) {
    return null
  }
  return sortedToBST(nums, 0, nums.length)
};

const sortedToBST = function (nums, start, end) {
  if (start === end) {
    return null
  }
  const mid = (start + end) >>> 1;
  let root = new TreeNode(nums[mid])
  root.left = sortedToBST(nums, start, mid);
  root.right = sortedToBST(nums, mid + 1, end);
  return root
}

Runtime: 96 ms, faster than 7.29% of JavaScript online submissions forConvert Sorted Array to Binary Search Tree.

Memory Usage: 37.7 MB, less than 52.11% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.

看到了一个更加简洁的做法，无需增加一个函数。只需要在当前函数进行迭代即可。

主要是middle不是通过设定的start和end来计算，而是直接通过长度除一下。因此也不需要额外送进去范围。

var sortedArrayToBST = function(nums) {
  if (nums.length === 0) {
    return null
  }
  const middle = Math.floor(nums.length / 2)
  const root = new TreeNode(nums[middle])
  root.left = sortedArrayToBST(nums.slice(0, middle))
  root.right = sortedArrayToBST(nums.slice(middle + 1, nums.length))

  return root
}

Runtime: 84 ms, faster than 16.19% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.

Memory Usage: 37.7 MB, less than 49.28% of JavaScript online submissions for Convert Sorted Array to Binary Search Tree.

迭代

有序数组，即意味着可以用二分法。

但是试了半天没有试出来。。。