leetcode

0 // Naive approach using vector to precompute in-order traversal

1

2 class BSTIterator {

3 vector<int> vec;

4 int current = 0;

5

6 public:

7 BSTIterator(TreeNode *root) {

8 stack<TreeNode *> st;

9 while (true) {

10 while (root) {

11 st.push(root);

12 root = root->left;

13 }

14 if (st.empty()) break;

15 root = st.top();

16 st.pop();

17 vec.push_back(root->val);

18 root = root->right;

19 }

20 }

21

22 int next() { return vec[current++]; }

23

24 bool hasNext() { return current < vec.size(); }

25 };

26

27 // Compute in-order on the fly

28

29 class BSTIterator {

30 stack<TreeNode *> st;

31

32 void fill_stack(TreeNode *root) {

33 while (root) {

34 st.push(root);

35 root = root->left;

36 }

37 }

38

39 public:

40 BSTIterator(TreeNode *root) { fill_stack(root); }

41

42 int next() {

43 int val = st.top()->val;

44 TreeNode *root = st.top()->right;

45 st.pop();

46 fill_stack(root);

47 return val;

48 }

49

50 bool hasNext() { return !st.empty(); }

51 };