【LeetCode 108】将有序数组转换为二叉搜索树

浅浅的花香味﹌ 2023-02-20 13:32 26阅读 0赞

#### 题目描述 ####

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

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

示例:

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

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

0
         / \
       -3   9
       /   /
     -10  5

#### 解题思路 ####

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

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

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

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

#### 代码实现 ####

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */
    /** * @param {number[]} nums * @return {TreeNode} */
    var sortedArrayToBST = function(nums) { 
       if(!nums.length){ 
           return null
       }
       function bst(low, high){ 
           // 遍历结束条件
           if(low>high){ 
               return null
           }
           // 取出当前子序列的中间元素的索引值
           const mid = Math.floor(low+(high-low)/2)
           // 将中间元素的值作为当前子树的根节点
           const cur = new TreeNode(nums[mid])
           // 递归构建左子树
           cur.left = bst(low, mid-1)
           // 递归构建右子树
           cur.right = bst(mid+1, high)
           return cur
       }
       return bst(0, nums.length-1)
    };

#### 提交结果 ####

![在这里插入图片描述][20200627114942407.png]

[20200627114942407.png]: https://img-blog.csdnimg.cn/20200627114942407.png