【LEETCODE】模拟面试-108-Convert Sorted Array to Binary Search Tree

图源：新生大学

题目：

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

分析：

Input: So we're given a sorted array in ascending order. **Output: ** To return the root of a Binary Search Tree.

The corner case is when the input array is null or empty, then we will return null.

To build a tree, we need to firstly find the root.

And since it's a BST, which means the difference between the height of left tree and right tree is no more than 1, the middle in the array will be taken as the root.

And the left part will construct the left tree, right part will be the right tree.

Then we move to the next level, again, we'll first find the parent which will be the middle in the left part of array, and the right tree will be processed as well.

According to this procedure, it's obvious that we can use Recursion to deal with this problem.

At each level, we find the middle of current array period. For next level, we will pass current 'middle' as left boundary and right boundary to right tree or left tree, until we move to an interval where its 'start' index is larger then 'end' index.

Here we got the code as followed:

The Time complexity is O(n), since we traverse every data in the array. The Space complexity is O(1), since we haven't applied any data structure. or we can say O(logn), since the recursion has its own stack space.

Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

public class Solution {
    public TreeNode sortedArrayToBST(int[] array){
        //corner case
        if ( array == null || array.length == 0 )
            return null;
        
        //core logic
        int n = array.length;
        return helper(array, 0, n-1);
    }
    
    private TreeNode helper(int[] array, int start, int end){
        //base case
        if ( start > end )
            return null;
        
        //current
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode( array[mid] );
        
        //next
        root.left = helper( array, start, mid - 1 );
        root.right = helper( array, mid + 1, end );
        
        return root;
    }
    
}