# Binary Search Tree Iterator ### Source - lintcode: [(86) Binary Search Tree Iterator](http://www.lintcode.com/en/problem/binary-search-tree-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. 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. Super Star: Extra memory usage O(1) ~~~ ### 題解 - 中序遍歷 仍然考的是中序遍歷，但是是非遞歸實現。其實這道題等價于寫一個二叉樹中序遍歷的迭代器。需要內置一個棧，一開始先存儲到最左葉子節點的路徑。在遍歷的過程中，只要當前節點存在右子樹，則進入右子樹，存儲從此處開始到當前子樹里最左葉子節點的路徑。 ### Java ~~~ /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } * Example of iterate a tree: * Solution iterator = new Solution(root); * while (iterator.hasNext()) { * TreeNode node = iterator.next(); * do something for node * } */ public class Solution { private Stack<TreeNode> stack = new Stack<>(); private TreeNode curt; // @param root: The root of binary tree. public Solution(TreeNode root) { curt = root; } //@return: True if there has next node, or false public boolean hasNext() { return (curt != null || !stack.isEmpty()); //important to judge curt != null } //@return: return next node public TreeNode next() { while (curt != null) { stack.push(curt); curt = curt.left; } curt = stack.pop(); TreeNode node = curt; curt = curt.right; return node; } } ~~~ ### 源碼分析 1. 這里容易出錯的是 `hasNext()` 函數中的判斷語句，不能漏掉 `curt != null`。 1. 如果是 leetcode 上的原題，由于接口不同，則不需要維護 current 指針。