- 108. Convert Sorted Array to balanced Binary Search Tree
- The tricky part is the base case .
- Write induction part first and then test arrays of different size, 0, 1,2, 3
- And finalize the base case
- /**
- * 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) {
- if(nums.length == 0){
- return null;
- }
- TreeNode root = helper(nums, 0, nums.length - 1); // nums.length - 1
- return root;
- }
- private TreeNode helper(int[] nums, int start, int end){
- // this base case, try 4 cases. When size is 0, 1, 2 , 3
- if(start> end) return null;
- int mid = start + (end - start) / 2;
- TreeNode root = new TreeNode(nums[mid]);
- root.left = helper(nums, start, mid - 1); // mid - 1
- root.right = helper(nums, mid + 1, end); // mid + 1
- return root;
- }
- }
来源: http://www.bubuko.com/infodetail-2730808.html