Java Iterative Solution


  • 40

    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;
        }
    
    }

  • 9
    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.


  • 0
    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


  • 0
    Z

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


Log in to reply
 

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