173. 二叉搜索树迭代器

二叉搜索树迭代器

这题的本质，就是通过非递归方式遍历树结构。

递归，内存中有栈这种结构存储以前的数据信息。如果采用非递归的形式，我们需要手动存储’递归’信息

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
	// 存储当前模拟递归遍历到的节点
    public TreeNode cur;
	// 模拟递归时的stack
    public Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
        cur = root;
        stack = new LinkedList<>();
    }
    
    // 模拟中序遍历
    /* if (root == null) return;
     * dfs(root.left);
     * System.out.println(node.val);
     * dfs(root.right);
     */
    public int next() {
        // dfs(left)
        while(cur != null) {
            stack.add(cur);
            cur = cur.left;
        }
        cur = stack.pollLast();
        // sout(cur) 
        int ans = cur.val;
        // 指向右节点 dfs(right)
        cur = cur.right;
        return ans;
    }
    
    public boolean hasNext() {
    	// 当前节点不为null, 表明还有节点需要遍历
    	// stack不为空, 表示中序的遍历走过的节点还没被遍历, 需要进行遍历
        return cur != null || !stack.isEmpty();
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */
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