Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/\
-3 9
/ /
-10 5
题目
把一个有序数组转换成二叉树，要求左右深度不能大于一。
思路
有这个深度要求，我们就只能从中间一分为二，对于左右子树，也同样一分为二，所以就是递归去做。
代码
public TreeNode sortedArrayToBST(int[] nums) {
if (nums==null) {
return null;
}
return convertTree(nums,0,nums.length-1);//递归函数
}
private TreeNode convertTree(int[] nums, int l, int r) {
if (l<=r) {
int mid =(l+r)/2;
TreeNode root=new TreeNode(nums[mid]);//取中间的值为根节点
root.left=convertTree(nums, l, mid-1);//递归获得左右子树
root.right=convertTree(nums, mid+1, r);
return root;
}else {
return null;
}
}
