LintCode (86) Binary Search Tree Inorder Traversal Iterator

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.

Have you met this question in a real interview? 

Yes

Example

For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]

   10
 /    \
1      11
 \       \
  6       12

Challenge

Extra memory usage O(h), h is the height of the tree.

这题和上一题，inorder traversal without recursion是一样的，做会了那题这题就好说了。

总是保持当前stk存的指针为最左， 所以判断has next就是判断stk是不是空，而获取next的时候，则返回stk最顶，但返回前需要继续向右孩子的最左遍历以保持最左面。 所以思想和上题是一致的。

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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } * Example of iterate a tree: * Solution iterator = Solution(root); * while (iterator.hasNext()) { * TreeNode * node = iterator.next(); * do something for node */ class Solution { public: //@param root: The root of binary tree. Solution(TreeNode *root) { // write your code here while(root){ stk.push(root); root=root->left; } } //@return: True if there has next node, or false bool hasNext() { // write your code here return !stk.empty(); } //@return: return next node TreeNode* next() { // write your code here if (stk.empty()) return 0; TreeNode* tmp=stk.top(); stk.pop(); TreeNode* cur; cur=tmp->right; while(cur){ stk.push(cur); cur=cur->left; } return tmp; } stack<TreeNode*> stk; };