Question: https://leetcode.com/problems/binary-search-tree-iterator/
Question Name: Binary Search Tree Iterator
The challenge is a variant of the iterative in-order traversal of BST. However, yield in python is much much better in implementing iterator, right?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | # Definition for a binary tree node # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class BSTIterator: # @param root, a binary search tree's root node def __init__(self, root): self.stack = [] current = root while current != None: self.stack.append(current) current = current.left return # @return a boolean, whether we have a next smallest number def hasNext(self): return len(self.stack) != 0 # @return an integer, the next smallest number def next(self): next_node = self.stack.pop() current = next_node.right while current != None: self.stack.append(current) current = current.left return next_node.val # Your BSTIterator will be called like this: # i, v = BSTIterator(root), [] # while i.hasNext(): v.append(i.next()) |