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
| class BSTIterator {
private Deque<TreeNode> stack;
public BSTIterator(TreeNode root) {
stack = new ArrayDeque<>();
loadNodes(root);
}
public int next() {
TreeNode topNode = stack.pop();
if (topNode.right != null) {
loadNodes(topNode.right);
}
return topNode.val;
}
public boolean hasNext() {
return !stack.isEmpty();
}
private void loadNodes(TreeNode node) {
TreeNode ptr = node;
while (ptr != null) {
stack.push(ptr);
ptr = ptr.left;
}
}
}
|
学会了如何iteratively in-order traversal. 分为装nodes以及pop nodes. 装的时候就把自己然后一直往左走, 把路过的nodes都装进栈, 直到往左走走到null. pop的时候, pop出来的node如果它的右node不是null, 那就load右node进栈并且重复刚才说的一直往左的过程.
时间复杂度: O(n) 每个node会被装进stack一次以及出栈一次. n是node的总个数.
空间复杂度: O(n)
