- 39.9%

https://leetcode.com/problems/binary-search-tree-iterator/#/description

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

方法一：

我的代码实现：

1 | /** |

https://discuss.leetcode.com/topic/6575/my-solutions-in-3-languages-with-stack

My solutions in 3 languages with Stack

I use Stack to store directed left children from root.

When next() be called, I just pop one element and process its right child as new root.

The code is pretty straightforward.

So this can satisfy O(h) memory, hasNext() in O(1) time,

But next() is O(h) time.

I can’t find a solution that can satisfy both next() in O(1) time, space in O(h).

Java:

1 | public class BSTIterator { |

C++:

1 | class BSTIterator { |

Python:

1 | class BSTIterator: |

https://discuss.leetcode.com/topic/12265/my-solution-in-c-in-average-o-1-time-and-uses-o-h-memory

My Solution in C++, in average O(1) time and uses O(h) memory

1 | class BSTIterator { |

https://discuss.leetcode.com/topic/8154/morris-traverse-solution

Morris traverse solution

Traverse a BST from the smallest to the largest, then i solve this question simply use the inorder traversal.

To implement a iterator means we should traverse the tree step by step, so just split the inorder traversal.

1 | class BSTIterator { |

https://discuss.leetcode.com/topic/24617/c-using-stack

C++. using stack.

1 | /** |

The basic idea behind this solution is that we have to implement inorder iteratively but it will gets split into two functions i.e. hasNext and next.

hasNext() will push all the left elements and check and return accordingly if elements are in the stack.

next() will just pop() the top element from the stack and update the current pointer to right .

For this we are taking a stack and a current pointer.

But maybe I may be wrong in hasNext as the requirement of question is O(1) for hasNext() as well.

Open for comments.

https://discuss.leetcode.com/topic/6629/two-python-solutions-stack-and-generator

Two Python solutions, stack and generator

stack solution:

1 | def __init__(self, root): |

generator solution:

1 | def __init__(self, root): |