Java Iterative Solution


  • 44

    I came up with the recursion solution first and tried to translate it into an iterative solution. It is very similar to doing a tree inorder traversal, I use three stacks - nodeStack stores the node I am going to process next, and leftIndexStack and rightIndexStack store the range where this node need to read from the nums.

    public class Solution {
        
        public TreeNode sortedArrayToBST(int[] nums) {
            
            int len = nums.length;
            if ( len == 0 ) { return null; }
            
            // 0 as a placeholder
            TreeNode head = new TreeNode(0); 
            
            Deque<TreeNode> nodeStack       = new LinkedList<TreeNode>() {{ push(head);  }};
            Deque<Integer>  leftIndexStack  = new LinkedList<Integer>()  {{ push(0);     }};
            Deque<Integer>  rightIndexStack = new LinkedList<Integer>()  {{ push(len-1); }};
            
            while ( !nodeStack.isEmpty() ) {
                TreeNode currNode = nodeStack.pop();
                int left  = leftIndexStack.pop();
                int right = rightIndexStack.pop();
                int mid   = left + (right-left)/2; // avoid overflow
                currNode.val = nums[mid];
                if ( left <= mid-1 ) {
                    currNode.left = new TreeNode(0);  
                    nodeStack.push(currNode.left);
                    leftIndexStack.push(left);
                    rightIndexStack.push(mid-1);
                }
                if ( mid+1 <= right ) {
                    currNode.right = new TreeNode(0);
                    nodeStack.push(currNode.right);
                    leftIndexStack.push(mid+1);
                    rightIndexStack.push(right);
                }
            }
            return head;
        }
    
    }

  • 11
    5

    Great idea. The recursion approach is quite boring and let me share my iterative solution using BFS. There is a queue under the hood. And also a small data type encapsulate necessary info. Briefly, we assemble the tree from upper level to lower level, from left sibling to rightmost sibling. I think it is straight forward.

        public class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            if (nums == null || nums.length == 0) {
                return null;
            }
            
            Queue<MyNode> queue = new LinkedList<>();
            int left = 0;
            int right = nums.length - 1;
            int val = nums[left + (right - left) / 2];
            TreeNode root = new TreeNode(val);
            queue.offer(new MyNode(root, left, right));
            
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    MyNode cur = queue.poll();
                    
                    int mid = cur.lb + (cur.rb - cur.lb) / 2;
                    
                    if (mid != cur.lb) {
                        TreeNode leftChild = new TreeNode(nums[cur.lb + (mid - 1 - cur.lb) / 2]);
                        cur.node.left = leftChild;
                        queue.offer(new MyNode(leftChild, cur.lb, mid - 1));
                    }
                    
                    if (mid != cur.rb) {
                        TreeNode rightChild = new TreeNode(nums[mid + 1 + (cur.rb - mid - 1) / 2]);
                        cur.node.right = rightChild;
                        queue.offer(new MyNode(rightChild, mid + 1, cur.rb));
                    }
                }
            }
            
            return root;
        }
        
        private static class MyNode {
            TreeNode node;
            int lb;
            int index;
            int rb;
            
            public MyNode(TreeNode n, int theLeft, int theRight) {
                this.node = n;
                this.lb = theLeft;
                this.rb = theRight;
            }
        }
    }
    

  • 0
    H
    public class MyNode{
        TreeNode node;
        int start;
        int end;
        
        public MyNode(int start, int end, TreeNode node){
            this.start = start;
            this.end = end;
            this.node = node;
        }
    }
    
    
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length ==0 ) return null;
        
        Stack<MyNode> stack = new Stack<MyNode>();
        int mid = 0 + (nums.length -1 - 0)/2;
        TreeNode root = new TreeNode(nums[mid]);
        MyNode MyRoot = new MyNode(0, nums.length -1, root);
        stack.push(MyRoot);
        while(!stack.isEmpty()){
            MyNode curr = stack.pop();
            int oldMid = curr.start + (curr.end - curr.start)/2;
            if(oldMid -1 >= curr.start){
                mid = curr.start + (oldMid-1 - curr.start)/2;
                root = new TreeNode(nums[mid]);
                stack.push(new MyNode(curr.start, oldMid - 1, root));
                curr.node.left = root;
            }
            
            if(oldMid +1 <= curr.end){
                mid = oldMid +1 + (curr.end - oldMid -1)/2;
                root = new TreeNode(nums[mid]);
                stack.push(new MyNode(oldMid + 1, curr.end, root));
                curr.node.right = root;
            }    
        }
        
        return MyRoot.node;
    }
    

    Use an inner class to save space


  • 1
    A

    You are actually doing a preorder traversal...


  • 0
    G

    @Adeath It's good to find someone who sees the same problem :) In this case any traversal used could solve the problem though.


  • 0
    C

    instead of using two index stack, or wrap them up in a wrapper class, could just merge them into one stack.


  • 1
    S

    @516364598chang Great solution. I'd argue that you don't even need the following lines inside the queue while :

    int size = queue.size();
            for (int i = 0; i < size; i++) {
    ...
    }
    

    The queue will pop all the nodes even without that loop and the function works fine.


  • 0
    B

    beats 0.94% why?
    slower than recursion


  • 1
    Z

    your program seems like dfs, but use same space as bfs, maybe we can reduce the use of space.


  • 0
    M

    Use a private class to make it more readable

    	private class Node {
    		TreeNode node;
    		int left, right;
    		public Node(TreeNode node, int left, int right) {
    			this.node = node;
    			this.left = left;
    			this.right = right;
    		}
    	}
    	public TreeNode sortedArrayToBST(int[] nums) {
    		if (nums == null || nums.length == 0) return null;
    		TreeNode root = new TreeNode(0);
    		Stack<Node> stack = new Stack<>();
    		Node node = new Node(root, 0, nums.length - 1);
    		stack.push(node);
    		while (!stack.isEmpty()) {
    			Node cur = stack.pop();
    			int mid = cur.left + (cur.right - cur.left) / 2;
    			cur.node.val = nums[mid];		
    			if (cur.left < mid) {
    				cur.left = new TreeNode(0);
    				stack.push(new Node(cur.left, cur.left, mid - 1));
    			}
    			if (cur.right > mid) {
    				cur.right = new TreeNode(0);
    				stack.push(new Node(cur.right, mid + 1, cur.right));
    			}
    		}
    		return root;
    	}
    
    

Log in to reply
 

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