Is there anybody can solve this problem without using recursion?


  • 1
    D

    Is there anybody can solve this problem without using recursion?And what is the time & space complexity?


  • 1
    B
    public TreeNode sortedArrayToBST(int[] num) {
            Queue<TreeNode> nodes = new LinkedList<TreeNode>();
            int length = num.length, i = 1 , c = 4, l = 0, r = 0, s = 1;
            int[] trace = new int[length];
            if (length == 0) {
                return null;
            }
            TreeNode root = new TreeNode(num[length/2]);
            nodes.add(root);
    
            //trace is to track if an element in num has been added to tree
            trace[length/2] = 1;
            while (s != length) {
                while (i < c) {
                    TreeNode n = nodes.poll();
                    if (n != null) {
                        // i / c = 1/4, 1/8, 5/8 ...
                        l = (i*length)/c; 
    
                        // (i+2) / c = 3/4, 3/8, 7/8...
                        r = (i+2)*length/c; 
                        TreeNode left = null, right = null;
                    
                        if (trace[l] != 1) {
                            s++;
                            trace[l] = 1;
                            left = new TreeNode(num[l]);
                        }    
                        if (trace[r] != 1) {
                            s++;
                            trace[r] = 1;
                            right = new TreeNode(num[r]);
                        }
                        n.left = left;
                        n.right = right;
                        nodes.add(left);
                        nodes.add(right); 
                    }
                    i += 4;
                }
                i = 1;
                c *= 2;
            }
            return root;
        }

  • 1
    G

    There is always a way to convert recursion to iterative. I have tried to use a queue and it seems working.
    Worst time: O(n), worst space O(n).

    private class NodeE extends TreeNode {
    	int i = 0;         //corresponding num index        
    	int iL = 0;        //left index of un-searched
    	int iR = 0;        //right index of un-searched
    	NodeE(int val, int i, int iL, int iR) {
    		super(val);
    		this.i = i;
    		this.iL = iL;
    		this.iR = iR;
    	}
    }
    
    public TreeNode sortedArrayToBST(int[] num) {
    	if (num == null || num.length == 0)
    		return null;
    	
    	Deque<NodeE> q = new ArrayDeque<NodeE>();
    	NodeE root = new NodeE(num[num.length / 2], num.length/2, 0, num.length - 1);
    	q.add(root);
    	
    	while (!q.isEmpty()) {
    		NodeE n = q.remove();
    		if (n.i > n.iL) { // left half, from iL to i - 1!
    			int nextI = (n.iL + n.i) / 2;
    			NodeE nL = new NodeE(num[nextI], nextI, n.iL, n.i -1);
    			q.add(nL);
    			n.left = nL;
    		}
    		if (n.i < n.iR) { // right half, from i + 1 to iR!
    			int nextI = (n.i + 1 + n.iR + 1) / 2;
    			NodeE nR = new NodeE(num[nextI], nextI, n.i + 1, n.iR);
    			q.add(nR);
    			n.right = nR;
    		}
    	}
    	return root;
    }

  • 0
    Z

    The i/c sequence is ingenious! @bravejia you have truly mastered math skills.


Log in to reply
 

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