108 Convert Sorted Array to Binary Search Tree

108. Convert Sorted Array to Binary Search Tree

1. Question

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

2. Implementation

(1) Recursion

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        return generateBST(nums, 0, nums.length - 1);
    }

    public TreeNode generateBST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        int mid = start + (end - start) / 2;
        TreeNode curNode = new TreeNode(nums[mid]);
        curNode.left = generateBST(nums, start, mid - 1);
        curNode.right = generateBST(nums, mid + 1, end);
        return curNode;
    }
}

(2) Iterative

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        TreeNode root = new TreeNode(0);
        Stack<TreeNode> nodes = new Stack<>();
        Stack<Integer> leftIndexes = new Stack<>();
        Stack<Integer> rightIndexes = new Stack<>();

        nodes.push(root);
        leftIndexes.push(0);
        rightIndexes.push(nums.length - 1);

        while (!nodes.isEmpty()) {
            TreeNode curNode = nodes.pop();
            int start = leftIndexes.pop();
            int end = rightIndexes.pop();

            int mid = start + (end - start) / 2;
            curNode.val = nums[mid];

            if (start <= mid - 1) {
                curNode.left = new TreeNode(0);
                nodes.push(curNode.left);
                leftIndexes.push(start);
                rightIndexes.push(mid - 1);
            }

            if (end >= mid + 1) {
                curNode.right = new TreeNode(0);
                nodes.push(curNode.right);
                leftIndexes.push(mid + 1);
                rightIndexes.push(end);
            }
        }
        return root;
    }
}

3. Time & Space Complexity

Recursion: 时间复杂度O(n), 空间复杂度: O(logn)

Iteration: 时间复杂度O(n), 空间复杂度: O(n)