86. Binary Search Tree Iterator(

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 进行相应的变化

挪到下一个点的算法如下：

• 如果当前点存在右子树，那么就是右子树中“一路向左”最左边的那个点

• 如果当前点不存在右子树，则是走到当前点的路径中，第一个左拐的点（这个判断十分重要）

代码：