Java O(n) Easy To Understand, Optimal Solution


  • 0
    B

    Explanation
    The point to this question is to use a Divide and Conquer approach when constructing a balanced BST. We define helper function recurse(...) that will split our subarray, from index lo to hi, into more or less 2 equal parts, if possible, since this will produce a balanced BST for us.

    Cases to Consider:

    1. If lo == hi, then we're creating a leaf node with value nums[lo]. We still need to recursively call recurse(...) on its left and right children to set them to null.
    2. If lo > hi, then we're returning null for a parent node.
    3. If lo < hi, then we're splitting the nums subarray from indices lo to hi in half, and we're recursively creating subtrees from them.

    Time Complexity
    The time complexity is O(n) where n is the size of nums, since our recurrence relation is T(n) = 2T(n/2) + O(1), which is equal to O(n) by Master Theorem.

    class Solution {
        public TreeNode recurse(int[] nums, int lo, int hi) {
            if (hi < lo) { return null; }
            int mid = (lo + hi)/2;
            // Create tree structure here
            TreeNode root = new TreeNode(nums[mid]);
            root.left = recurse(nums, lo, mid - 1);
            root.right = recurse(nums, mid + 1, hi);
            return root;
        }
        
        public TreeNode sortedArrayToBST(int[] nums) {
            return recurse(nums, 0, nums.length - 1);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.