題目:
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
題解:
和我上面一篇将有序連結清單轉成二叉排序樹中用哈希表解的方法是一樣的,基本思路:連結清單中間那個節點為樹的根節點,根節點的左子樹節點應該是根節點左邊那部分的中間節點,根節點的右節點應該是根節點右邊那部分連結清單的中間節點,後面就按照這個規律依次類推了。
public static TreeNode sortedArrayToBST(int[] nums) {
int end=nums.length;
if(end<=0)
return null;
return buildTree(nums, 0, end-1);//因為從0開始計數 是以減一
}
public static TreeNode buildTree(int[] nums,int start,int end)
{
if(start<=end)
{
int mid=(start+end)/2;
TreeNode root=new TreeNode(nums[mid]);
root.left=buildTree(nums, start, mid-1);
root.right=buildTree(nums, mid+1, end);
return root;
}
else {
return null;
}
}