# 108. 将有序数组转换为二叉搜索树
# 题目
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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
11
2
3
4
5
6
7
8
9
10
11
# 题解
# 中序遍历 + 始终选择中间位置右边元素作为根节点
/**
* 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) {
function helper(l, r) {
if (l > r) return null;
let mid = ~~((l + r) / 2);
if ((l + r) % 2) {
mid++;
}
// 中序遍历
const root = new TreeNode(nums[mid]);
root.left = helper(l, mid - 1);
root.right = helper(mid + 1, r);
return root;
}
return helper(0, nums.length - 1);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27