Solution by dilyar


  • 0

    Approach #1 Tail-Recursive Solution [Accepted]

    Algorithm

    The key idea is to use two pointer and recursive method to help construct the BST.
    We init the root node and then set its left and right subtree with corresponding indices.
    Because of recursive calls on the helper() method, we will have a BST at the end.

    Java

    public class Solution {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
        public TreeNode sortedArrayToBST(int[] nums) {
            if (nums == null || nums.length == 0) return null;
            return helper(nums, 0, nums.length - 1);
        }
    
        private TreeNode helper(int[] nums, int left, int right) {
            if (left > right) return null;
            int mid = (left + right) / 2;
            TreeNode node = new TreeNode(nums[mid]);
            node.left = helper(nums, left, mid - 1);
            node.right = helper(nums, mid + 1, right);
            return node;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$, where n is the length of given array.

    • Space complexity : $$O(n)$$. The recursive function is called n times in the method stack.


Log in to reply
 

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