LeetCode - Binary Search Tree Iterator

 1 // 1CE, 1MLE, 1WA, 1AC, anonther good problem
 2 #include <unordered_map>
 3 using namespace std;
 4 /**
 5  * Definition for binary tree
 6  * struct TreeNode {
 7  *     int val;
 8  *     TreeNode *left;
 9  *     TreeNode *right;
10  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
11  * };
12  */
13 class BSTIterator {
14 public:
15     BSTIterator(TreeNode *root) {
16         nn.clear();
17         currentNode = nullptr;
18         
19         if (root == nullptr) {
20             return;
21         }
22         
23         TreeNode *ll, *rr;
24         findSuccessor(root, ll, rr);
25         currentNode = ll;
26     }
27 
28     /** @return whether we have a next smallest number */
29     bool hasNext() {
30         return currentNode != nullptr;
31     }
32 
33     /** @return the next smallest number */
34     int next() {
35         int val = currentNode->val;
36         currentNode = nn[currentNode];
37         return val;
38     }
39     
40     ~BSTIterator() {
41         nn.clear();
42     }
43 private:
44     unordered_map<TreeNode *, TreeNode *> nn;
45     TreeNode *currentNode;
46     
47     void findSuccessor(TreeNode *root, TreeNode *&left, TreeNode *&right) {
48         TreeNode *ll, *lr, *rl, *rr;
49         
50         if (root->left == nullptr) {
51             ll = root;
52             lr = root;
53         } else {
54             findSuccessor(root->left, ll, lr);
55             nn[lr] = root;
56         }
57         
58         if (root->right == nullptr) {
59             rl = root;
60             rr = root;
61         } else {
62             findSuccessor(root->right, rl, rr);
63             nn[root] = rl;
64         }
65         left = ll;
66         right = rr;
67     }
68 };
69 
70 /**
71  * Your BSTIterator will be called like this:
72  * BSTIterator i = BSTIterator(root);
73  * while (i.hasNext()) cout << i.next();
74  */