108. Convert sorted array to binary search tree

Hits: 0

Given an [array] nums of integers, where the elements are already in ascending order, please convert it into a height-balanced binary search tree.

A height-balanced binary tree is a binary tree that satisfies “the absolute value of the height difference between the left and right subtrees of each node does not exceed 1”.

Example 1:

Input: nums = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null ,9] would also be considered the correct answer:

Method 1:
Recursion, starting from the middle element of the array (satisfying the [balanced binary tree] ) to construct a binary tree recursively, and construct it in the order of in-order traversal.

Code:

class  Solution {
     public TreeNode sortedArrayToBST ( int [] nums ) {
         // recursively build the binary tree starting from the middle node of the array (for building a balanced binary search tree) 
        return helper(nums, 0 , nums.length - 1 );
    }

    TreeNode helper(int[] nums, int l, int r) {
        if (l > r) return null;

        int mid = l + (r - l) / 2 ; // get the middle node 
        TreeNode head = new TreeNode(nums[mid]);
        head.left = helper(nums, l, mid - 1);
        head.right = helper(nums, mid + 1, r);

        return head;
    }
}

Time Complexity: O(lgn)
Space Complexity: O(n) Store all elements

You may also like...

Leave a Reply

Your email address will not be published.