173. Binary Search Tree Iterator

``` ``` <div class="elfjS" data-track-load="description_content" style="">Implement the <code>BSTIterator</code> class that represents an iterator over the <a href="https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR)" target="_blank">in-order traversal</a> of a binary search tree (BST): <ul> <li style=""><code style="">BSTIterator(TreeNode root)</code> Initializes an object of the <code>BSTIterator</code> class. The <code>root</code> of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.</li> <li><code>boolean hasNext()</code> Returns <code>true</code> if there exists a number in the traversal to the right of the pointer, otherwise returns <code>false</code>.</li> <li><code>int next()</code> Moves the pointer to the right, then returns the number at the pointer.</li> </ul> Notice that by initializing the pointer to a non-existent smallest number, the first call to <code>next()</code> will return the smallest element in the BST. You may assume that <code>next()</code> calls will always be valid. That is, there will be at least a next number in the in-order traversal when <code>next()</code> is called.   Example 1: <img alt="" src="https://assets.leetcode.com/uploads/2018/12/25/bst-tree.png" style="width: 189px; height: 178px;"> <pre>Input ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []] Output [null, 3, 7, true, 9, true, 15, true, 20, false] Explanation BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]); bSTIterator.next(); // return 3 bSTIterator.next(); // return 7 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 9 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 15 bSTIterator.hasNext(); // return True bSTIterator.next(); // return 20 bSTIterator.hasNext(); // return False </pre>   Constraints: <ul> <li>The number of nodes in the tree is in the range <code>[1, 105]</code>.</li> <li><code>0 <= Node.val <= 106</code></li> <li>At most <code>105</code> calls will be made to <code>hasNext</code>, and <code>next</code>.</li> </ul>   Follow up: <ul> <li>Could you implement <code>next()</code> and <code>hasNext()</code> to run in average <code>O(1)</code> time and use <code>O(h)</code> memory, where <code>h</code> is the height of the tree?</li> </ul> </div> --- ## Python solution 1: (cannot match problem requirement) - inoder紀錄中續遍歷的結果 - space為O(n): n為root總數 ```python= class BSTIterator(object): def __init__(self, root): """ :type root: TreeNode """ self.stack=[] self.inorder(root) def inorder(self,root): if not root: return self.inorder(root.left) self.stack.append(root) self.inorder(root.right) def next(self): """ :rtype: int """ ans=self.stack.pop(0) return ans.val def hasNext(self): """ :rtype: bool """ return True if self.stack else False ``` --- ## Python solution 2: (match problem requirement) 因為要求 O(h) space : h為樹高 space : O(h) Time : O(1) - init - 將左子逐一加入stack中 - next - 因為inorder性質，要先拜訪左子 - return_node = self.stack.pop() 即為解 - 判斷next_node是否有右子next_node, 有的話就一直往下找左子樹並加入stack ```python= class BSTIterator: def __init__(self, root: Optional[TreeNode]): self.stack = [] node = root while node: self.stack.append(node) node = node.left def next(self) -> int: return_node = self.stack.pop() next_node = return_node.right while next_node: self.stack.append(next_node) next_node = next_node.left return return_node.val def hasNext(self) -> bool: return len(self.stack) > 0 # Your BSTIterator object will be instantiated and called as such: # obj = BSTIterator(root) # param_1 = obj.next() # param_2 = obj.hasNext() ```