173 Binary Search Tree Iterator

173. Binary Search Tree Iterator​
1. Question
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Callingnext()will return the next smallest number in the BST.
Note:next()andhasNext()should run in average O(1) time and uses O(h) memory, wherehis the height of the tree.
2. Implementation
思路: 其实就是Inorder Traversal分解成next() 和 hasNext()两个function
1
public class BSTIterator {
2
    TreeNode curNode = null;
3
    Stack<TreeNode> stack = null;
4
​
5
    public BSTIterator(TreeNode root) {
6
        curNode = root;
7
        stack = new Stack<>();
8
    }
9
​
10
    /** @return whether we have a next smallest number */
11
    public boolean hasNext() {
12
        return !stack.isEmpty() || curNode != null;
13
    }
14
​
15
    /** @return the next smallest number */
16
    public int next() {
17
        while (curNode != null) {
18
            stack.push(curNode);
19
            curNode = curNode.left;
20
        }
21
        TreeNode temp = stack.pop();
22
        curNode = temp.right;
23
        return temp.val;
24
    }
25
}
26
​
27
/**
28
 * Your BSTIterator will be called like this:
29
 * BSTIterator i = new BSTIterator(root);
30
 * while (i.hasNext()) v[f()] = i.next();
31
 */
Copied!
3. Time & Space Complexity
hasNext()时间复杂度是O(1), next()时间复杂度是O(n), 平均时间复杂度是O(1), 空间复杂度是O(h)

155 Min Stack

224 Basic Calculator

Last modified 2yr ago

Copy link

Contents

173. Binary Search Tree Iterator

1. Question

2. Implementation

3. Time & Space Complexity

173. Binary Search Tree Iterator​

1. Question

2. Implementation

3. Time & Space Complexity

173. Binary Search Tree Iterator