二叉查找树迭代器_怎么用迭代器iterator来遍历二叉树

描述

设计实现一个带有下列属性的二叉查找树的迭代器：
next()返回BST中下一个最小的元素

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

样例

样例 1：

输入：

tree = {10,1,11,#,6,#,12}
1

输出：

[1,6,10,11,12]
1

解释：

二叉查找树如下 :
  10
/       \
1     11
  \       \
  6       12
可以返回二叉查找树的中序遍历 [1,6,10,11,12]

实现要点

递归 → 非递归，意味着自己需要控制原来由操作系统控制的栈的进进出出如何找到最小的第一个点？最左边的点即是。
如何求出一个二叉树节点在中序遍历中的下一个节点？
在 stack 中记录从根节点到当前节点的整条路径，下一个点=右子树最小点 or 路径中最近一个通过左子树包含当前点的点

代码

/**
 * 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.
    */
    private Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root) {
        // do intialization if necessary
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    /**
     * @return: True if there has next node, or false
     */
    public boolean hasNext() {
        // write your code here
        return !stack.isEmpty();
    }

    /**
     * @return: return next node
     */
    public TreeNode next() {
        TreeNode curt = stack.peek();
        TreeNode node = curt;

        if (node.right == null) {
            node = stack.pop();
            //下一个点=右子树最小点 or 路径中最近一个通过左子树包含当前点的点
            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;
    }
}
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
53
54
55
56
57
58
59
60
61
62
63