Easy to understand Java iterative solution.


  • 0
    N

    Basically doing level order traversal with extra 2 queues keeping track of left and right index range of each node.

    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        
        TreeNode root = new TreeNode(nums[(nums.length - 1) / 2]);
        Queue<TreeNode> nodes = new LinkedList<>();
        Queue<Integer> leftIdx = new LinkedList<>();
        Queue<Integer> rightIdx = new LinkedList<>();
        
        nodes.offer(root);
        leftIdx.offer(0);
        rightIdx.offer(nums.length - 1);
        
        while (!nodes.isEmpty()) {
            int size = nodes.size();
            for (int i = 0; i < size; ++i) {
                TreeNode node = nodes.poll();
                int left = leftIdx.poll();
                int right = rightIdx.poll();
                int mid = left + (right - left) / 2;
                if (left <= mid - 1) {
                    TreeNode nodeLeft = new TreeNode(nums[left + (mid - 1 - left) / 2]);
                    node.left = nodeLeft;
                    nodes.offer(nodeLeft);
                    leftIdx.offer(left);
                    rightIdx.offer(mid - 1);
                }
                
                if (right >= mid + 1) {
                    TreeNode nodeRight = new TreeNode(nums[mid + 1 + (right - mid - 1) / 2]);
                    node.right = nodeRight;
                    nodes.offer(nodeRight);
                    leftIdx.offer(mid + 1);
                    rightIdx.offer(right);
                }
            }
        }
        
        return root;
    }

Log in to reply
 

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