next() and hasNext() queries run in O(1) time in average.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]
/**
* 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 {
private Stack<TreeNode> stack = new Stack<>();
// @param root: The root of binary tree.
public BSTIterator(TreeNode root) {
while (root != null) {
stack.push(root);
root = root.left;
}
}
//@return: True if there has next node, or false
public boolean hasNext() {
return !stack.isEmpty();
}
//@return: return next node
public TreeNode next() {
TreeNode curt = stack.peek();
TreeNode node = curt;
// move to the next node
if (node.right == null) {
node = stack.pop();
while (!stack.isEmpty() && stack.peek().right == node) {
node = stack.pop();
}
} else {
node = node.right;
while (node != null) {
stack.push(node);
node = node.left;
}
}
return curt;
}
}
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]
Extra memory usage O(h), h is the height of the tree.
Super Star: Extra memory usage O(1)
思路：
这是一个非常通用的利用 stack 进行 Binary Tree Iterator 的写法。
stack 中保存一路走到当前节点的所有节点，stack.peek() 一直指向 iterator 指向的当前节点。
因此判断有没有下一个，只需要判断 stack 是否为空
获得下一个值，只需要返回 stack.peek() 的值，并将 stack 进行相应的变化，挪到下一个点。
挪到下一个点的算法如下：
访问所有节点用时O(n)，所以均摊下来访问每个节点的时间复杂度时O(1)
原文：https://www.cnblogs.com/FLAGyuri/p/12078541.html