115.Convert Sorted Array to Binary Search Tree

1022 단어
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
분석: 귀속적인 사상을 채택하다.먼저 뿌리 결점을 찾은 다음에 왼쪽 나무의 뿌리 결점과 오른쪽 나무의 뿌리 결점을 찾았다.
/**
	 * Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
	 * 
	 *  , root , 。
	 * 
	 * @date 20160423
	 * @param nums
	 * @return
	 */
	 public TreeNode sortedArrayToBST(int[] nums) {
		 int len = nums.length;
		 if(len <= 0){
			 return null;
		 }else{
			 return sortedArrayToBSTRecu(nums,0,len-1);
		 }
		 
	 }
	 /**@
	  *  nums[low,high] 
	  * @param nums
	  * @param low
	  * @param high
	  * @return
	  */
	 public TreeNode sortedArrayToBSTRecu(int[] nums,int low,int high){
		 int len = high-low+1;
		 if(len<=0){
			 return null;
		 }else{
			 int mid = low+(high-low)/2;
			 TreeNode root = new TreeNode(nums[mid]);
			 root.left = sortedArrayToBSTRecu(nums,low,mid-1);
			 root.right = sortedArrayToBSTRecu(nums,mid+1,high);
			 return root;
		 }
	 }

좋은 웹페이지 즐겨찾기