LeetCode 108. Convert Sorted Array to Binary Search Tree

Question

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

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

Solution

• Solution1

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }
    public TreeNode helper(int[] nums, int start, int end){
        if(start > end) return null;
        int mid = start + (end - start)/ 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, start, mid - 1);
        root.right = helper(nums, mid + 1, end);
        return root;
    }
}

Complexity:

Time complexity: O(n)

Space complexity: O(logn)