1ms Java solution, O(1) space, in-place


  • 3
    Y
    public class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            // 1:58pm - 2:02pm
            // divide-and-conquer
            // divide at the mid number, and then construct left and right sub trees recursively
            return helper(nums, 0, nums.length-1);
        }
        
        private TreeNode helper(int[] nums, int left, int right) {
            if (nums == null || left > right) {
                return null;
            }
            int mid = left + (right - left) / 2;
            TreeNode root = new TreeNode(nums[mid]);
            root.left = helper(nums, left, mid-1);
            root.right = helper(nums, mid+1, right);
            return root;
        }
    }

  • 2
    A

    This is recursion, which is obviously not a O(1) space solution.


Log in to reply
 

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