108. Convert Sorted Array to Binary Search Tree
Given an integer array nums
where the elements are sorted in ascending order, convert it to a
*height-balanced*
binary search tree.
Example 1:
Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:
Example 2:
Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums
is sorted in a strictly increasing order.solution
首先题目要求高度平衡,所谓的高度平衡,就是左右节点的高度差不超过 1,这道题目也是一个建树的问题。
那最简单的方法,我们发现给的是有序数组,因此我们为了平衡,就取最中间的数字作为根节点 如果是偶数数组,就是相差1,如果是奇数数组,就是刚好相等。
var sortedArrayToBST = function(nums) {
return buildTree(0,nums.length-1,nums);
};
function buildTree(l,r,nums){
if(l > r) return null;
let mid = (l+r) >> 1;
let node = new TreeNode(nums[mid]);
node.left = buildTree(l,mid-1,nums);
node.right = buildTree(mid+1,r,nums);
return node;
}