Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
题意:给定一个升序的数组,把这个数组转变成一个高度平衡的二叉搜索树。
思路:
题目要求高度平衡,所以需要我们把数组的中点位置当做根节点。
由于二叉搜索树的中序遍历结果就是升序,且左子树所有点的值小于根节点,因此中点位置左边是构成左子树的区间,右边是构成右子树的区间,求左右子树的过程递归执行就可以了。
public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
return helper(0, nums.length - 1, nums);
}
public TreeNode helper(int start, int end, int[] nums) {
if (start > end) {
return null;
}
int middle = start + (end - start) / 2;
TreeNode root = new TreeNode(nums[middle]);
root.left = helper(start, middle - 1, nums);
root.right = helper(middle + 1, end, nums);
return root;
}