LeetCode 173. Binary Search Tree Iterator

LeetCode 173

最简单的方法就是，先把树flatten中序遍历成一个list，然后在next中逐个返回。

但是note中有一个条件，空间复杂度只能是O（h），那么我们不能把整个树转为list存下来。

第一个想到的就是利用stack来做中序遍历，中序遍历基于stack的方法是：

def inOrder(root): 
    current = root  
    stack = [] 
     
    while True: 
        if current is not None: 
            stack.append(current)         
            current = current.left             
        elif(stack): 
            current = stack.pop() 
            print(current.data, end=" ") 
            current = current.right  
        else: 
            break
           

基于这个，我们可以把iterator实现成：

class BSTIterator:

    def __init__(self, root: TreeNode):        
        node = root
        self.stack = []
        while node:
            self.stack.append(node)
            node = node.left

    def next(self) -> int:
        """
        @return the next smallest number
        """
        result = self.stack.pop()
        if result.right:
            node = result.right
            while node:
                self.stack.append(node)
                node = node.left

        return result.val

    def hasNext(self) -> bool:
        """
        @return whether we have a next smallest number
        """
        return len(self.stack) > 0