将有序数组转换为二叉搜索树-简单
难度：简单
题目描述：
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树*每个节点 *的左右两个子树的高度差的绝对值不超过 1。
示例：
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
解题思路：
递归构建每个子树。将数组从最中间项分割得到三个部分：子数组 1，中间项，子数组 2。将中间项作为当前节点的 val，对子数组 1 和子数组 2 分别递归执行原方法，得到的两个子树分别作为上一个节点的左子树与右子树
var sortedArrayToBST = function (nums) {
if (!nums.length) return null;
const mid = Math.floor(nums.length / 2);
const root = new TreeNode(nums[mid]);
// subtrees are BSTs as well
root.left = sortedArrayToBST(nums.slice(0, mid));
root.right = sortedArrayToBST(nums.slice(mid + 1));
return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12