Convert Sorted Array to Binary Search Tree
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
给定一个排好序的数组,构造一颗平衡的二叉搜索树。我们可以每次都取数组的中间点作为当前子树的根节点,递归完成。代码如下:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
if(nums == null || nums.length == 0) return null;
int l = 0;
int r = nums.length - 1;
int m = l + (r - l) / 2;
TreeNode root = new TreeNode(nums[m]);
root.left = sortedArrayToBST(Arrays.copyOfRange(nums, 0, m));
root.right = sortedArrayToBST(Arrays.copyOfRange(nums, m + 1, nums.length));
return root;
}
}