Python solution using in-order tracing with while loop


  • 0
    M
    class BSTIterator(object):
        def __init__(self, root):
            self.treeList=[];
            
            if root!=None:
                cur=root;
                self.treeList.append(cur);
            
                while cur.left!=None:
                    self.treeList.append(cur.left);
                    cur=cur.left;
    
        def hasNext(self):
            if self.treeList==[]:
                return False;
            else:
                return True;
            
    
        def next(self):
            p=self.treeList.pop();
    
            if p.right!=None:
                self.treeList.append(p.right);
                tp=p.right;
                while tp.left!=None:
                    self.treeList.append(tp.left);
                    tp=tp.left;
    
            return p.val;
    

    This solution will push all the left children first. And for a node with right children, return the value and push all the left children of the right children to the stack. This is actually the inorder BST tracing using while loop.


Log in to reply
 

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