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

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

题目描述

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

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

示例：

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

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

       0
     /   \
   -3     9
   / \    /
 -10  n  5

我们再来看一个示例

示例2:

nums = [1,2,3,4,5,6,7,8,9,10,11,12], length = 12

             7
           /   \
          4     10
         /  \    / \
        2    6   9  12
       / \  / \  /\  /
      1  3 5  n 8  n 11

分析

上面 n 代表的是null, 我们直接看示例2的根节点的排列情况

• 7 的index 为 Math.floor(nums.length / 2)
  • 4 的index 为 1~7的一半， 我们称为左半边的一半
  • 10 的index 为 8~12的一半，我们称为右半边的一半

所以我们总结上面获取根节点的情况是nums[Math.floor(nums.length / 2)],然后反复获取左右半数组进行截取，再获取根节点，这里是一次递归

• 当nums.length 为0 的时候，我们返回null
• 根节点的左边数组为左子节点，右数组为右子节点

我们模拟一下nums = [1,2,3]的时候

• 我们取root = new TreeNode(nums[Math.floor(nums.length / 2)])即为2当根节点。当前左数组为[1], 右半数组为[3]
• 左节点 应该是左半数组组成的左子树, 左半数组剩下[1], 当前子树root = new TreeNode(nums[Math.floor(nums.length / 2)]), 所以根节点为1, 而后当前左右数组都为[], 再来root.left = 回到第一步
  • 当前数组的长度为0, 所以root.left = null, 所以整个流程是root = 2, root.left = 1, root.left.left = null
• 右节点跟左节点一样

源码

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

var sortedArrayToBST = function(nums) {
    //如果当前length 为奇数的话，那切一半，length / 2 + 1 为当前root，偶数为 length / 2
    const root = half(nums)
    return root;
};

var half = function(nums) {
    if(nums.length == 0) {
        return null
    }

    const currentIndex = Math.floor(nums.length / 2);
    const rootValue = nums[currentIndex];
    const currentRoot = new TreeNode(rootValue)
    // 分治
    let left = nums.slice(0, currentIndex);
    let right = nums.slice(currentIndex + 1);
    currentRoot.left = half(left);
    currentRoot.right = half(right);
    return currentRoot;
}