Is there any good iterative O(1) space solution out there?


  • 1
    S

    I understand that this problem can be most naturally solved with recursion. However, I wonder if there is an iterative solution that only uses constant space (aside from the space occupied by the input array and the output tree nodes). For now, the only thing I can think of is Morris Traversal, but I wonder if a simpler solution exists for this particular problem. Any suggestion would be appreciated!


  • -2
    S

    How do you like this? It's a recursive way, but it doesn't require copy stuff around but just constructs the tree based on given num. I LOVE Python. =)

    class Solution:
    # @param num, a list of integers
    # @return a tree node
    def sortedArrayToBST(self, num):
        
        def convert_array(left, right):
            """Convert num[left:right] to a (sub)tree."""
            
            # num[x:x] is an empty list (x is any number)
            if left >= right:
                return None
            
            # mid point at the very middle of num[left:right]
            # or the right one of the middle two
            mid = (left + right) / 2
    
            root = TreeNode(num[mid])
            root.left = convert_array(left, mid)
            root.right = convert_array(mid + 1, right)
    
            return root
        
        return convert_array(0, len(num))

  • 0
    D

    While this solution works great on my local machine, OJ is spitting run time error.


  • 0
    I

    It passed OJ before. I'd guess they might add a test case where num is None, and len(None) would raise TypeError.


  • 0
    D

    Isn't this a recursive solution? Somebody help me out here?


  • 0
    W

    Build the complete binary tree structure first, then use standard Morris traverse to assign value on each node.

    public TreeNode sortedArrayToBST(int[] nums) {
            int len = nums.length;
            if(len==0){
                return null;
            }
            
            TreeNode root = new TreeNode(0);
            len--;
            
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            
            int layer = 1;
            while(len>0){
                layer *= 2;
                for(int i=0;i<layer&&len>0;i++,len-=2){
                    TreeNode cur = q.poll();
                    cur.left = new TreeNode(0);
                    if(len>1){
                        cur.right = new TreeNode(0);
                        q.add(cur.left);
                        q.add(cur.right);
                    }
                }
            }
            
            int i=0;
            TreeNode cur = root;
            while(cur!=null){
                if(cur.left==null){
                    cur.val = nums[i++];
                    cur = cur.right;
                }else {
                    TreeNode pre = cur.left;
                    while(pre.right!=null && pre.right!=cur){
                        pre = pre.right;
                    }
                    
                    if(pre.right==null){
                        pre.right = cur;
                        cur = cur.left;
                    }else {
                        pre.right = null;
                        
                        // pre must has a value now
                        cur.val = nums[i++];
                        cur = cur.right;
                    }
                }
            }
            
            return root;
        }
    

Log in to reply
 

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