Description
Design an iterator over a binary search tree with the following rules:
Elements are visited in ascending order (i.e. an in-order traversal)
next() and hasNext() queries run in O(1) time in average.
Example
Example 1
Input: {10,1,11,#,6,#,12}
Output: [1, 6, 10, 11, 12]
Explanation:
The BST is look like this:
10
/\
1 11
\ \
6 12
You can return the inorder traversal of a BST [1, 6, 10, 11, 12]
Example 2
Input: {2,1,3}
Output: [1,2,3]
Explanation:
The BST is look like this:
2
/ \
1 3
You can return the inorder traversal of a BST tree [1,2,3]
Challenge
Extra memory usage O(h), h is the height of the tree.
Super Star: Extra memory usage O(1)
思路：
该 Iterator 算法即 non-recursion 的 inorder traversal，不仅仅适用于 BST，任何 Binary Tree 都可以
• stack 中保存一路走到当前节点的所有节点
• stack的栈顶 一直存储 iterator 指向的当前节点
• hasNext() 只需要判断 stack 是否为空
• next() 只需要返回 stack 的栈顶值，并将 iterator 挪到下一个点，对 stack 进行相应的变化
挪到下一个点的算法如下：
• 如果当前点存在右子树，那么就是右子树中“一路向左”最左边的那个点
• 如果当前点不存在右子树，则是走到当前点的路径中，第一个左拐的点（这个判断十分重要）
代码：
网友评论