【题目】
给出的升序排序的数组,个数必为奇数,要求形成二叉搜索(平衡)树。
【思路】
辅助函数fun,[0,len]=>[0,mid-1]+[mid+1,len]。
当left>right,返回null。
public TreeNode fun(int[] nums,int left,int right) {
int mid=(right+left)/2;
TreeNode tmp=new TreeNode(nums[mid]);
if(right<left)
return null;
tmp.left=fun(nums,left,mid-1);
tmp.right=fun(nums,mid+1,right);
return tmp;
}
【AC代码】
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
int len=nums.length;
if(nums.length==0){
return null;
}
TreeNode root=fun(nums,0,len-1);
return root;
} public TreeNode fun(int[] nums,int left,int right) {
int mid=(right+left)/2;
TreeNode tmp=new TreeNode(nums[mid]);
if(right<left)
return null;
tmp.left=fun(nums,left,mid-1);
tmp.right=fun(nums,mid+1,right);
return tmp;
}
}