lintcode(86)二叉查找树迭代器

Description:

设计实现一个带有下列属性的二叉查找树的迭代器：

元素按照递增的顺序被访问（比如中序遍历）next()和hasNext()的询问操作要求均摊时间复杂度是O(1)

Explanation:

对于下列二叉查找树，使用迭代器进行中序遍历的结果为 [1, 6, 10, 11, 12]

10 / \ 1 11 \ \ 6 12

Challenge:

额外空间复杂度是O(h)，其中h是这棵树的高度

Super Star：使用O(1)的额外空间复杂度

 Solution:

使用堆栈记录当前root 中序遍历的路径，将左节点从上至下推入到堆栈中。

堆栈非空，则有下一个节点。

next就是将堆栈中的节点依次进行中序遍历，返回当前节点，并将后来中序遍历的左节点推入栈中。

/** * 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: * BSTIterator iterator = new BSTIterator(root); * while (iterator.hasNext()) { * TreeNode node = iterator.next(); * do something for node * } */ public class BSTIterator { //@param root: The root of binary tree. Stack<TreeNode> tree = new Stack<TreeNode>(); public BSTIterator(TreeNode root) { // write your code here while(root != null){ tree.push(root); root = root.left; } } //@return: True if there has next node, or false public boolean hasNext() { // write your code here return !tree.isEmpty(); } //@return: return next node public TreeNode next() { // write your code here TreeNode result = tree.pop(); TreeNode current = result; if(current.right != null){ current = current.right; while(current != null){ tree.push(current); current = current.left; } } return result; } }