leetcode 108. Convert Sorted Array to Binary Search Tree

Seawolf

1. Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
   
2. 
   
3. 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.
   
4. 
   
5. Example:
   
6. 
   
7. Given the sorted array: [-10,-3,0,5,9],
   
8. 
   
9. One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
   
10. 
    
11.       0
    
12.      / \
    
13.    -3   9
    
14.    /   /
    
15. -10  5

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     public TreeNode sortedArrayToBST(int[] nums) {
    
12.         if(nums.length == 0) return null;
    
13.         int start = 0;
    
14.         int end = nums.length - 1;
    
15.         TreeNode node = helper(nums,start,end);
    
16.         return node;
    
17.         
    
18.     }
    
19.    
    
20.     public TreeNode helper(int[] nums, int start, int end){
    
21.         if(start > end) return null;
    
22.         int mid = (start + end)/2;
    
23.         TreeNode node = new TreeNode(nums[mid]);
    
24.         node.left = helper(nums,start,mid-1);
    
25.         node.right = helper(nums,mid+1,end);
    
26.         
    
27.         return node;
    
28.     }
    
29. }

复制代码