FilesExpand file tree

 master

/

173_BinarySearchTreeIterator173.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

65 lines (54 loc) · 1.52 KB

 master

/

173_BinarySearchTreeIterator173.java

Copy path

Top

File metadata and controls

• Code
• Blame

65 lines (54 loc) · 1.52 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

60

61

62

63

/**

* Implement an iterator over a binary search tree (BST). Your iterator will be

* initialized with the root node of a BST.

*

* Calling next() will return the next smallest number in the BST.

*

* Note: next() and hasNext() should run in average O(1) time and uses O(h)

* memory, where h is the height of the tree.

*

*/

/**

* Definition for binary tree

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class BinarySearchTreeIterator173 {

class BSTIterator {

private Stack<TreeNode> stack = new Stack();

public BSTIterator(TreeNode root) {

if (root != null) {

addAllLeft(root);

}

}

private void addAllLeft(TreeNode node) {

while (true) {

this.stack.push(node);

node = node.left;

if (node == null) return;

}

}

/** @return whether we have a next smallest number */

public boolean hasNext() {

return !this.stack.isEmpty();

}

/** @return the next smallest number */

public int next() {

TreeNode tmp = this.stack.pop();

int returned = tmp.val;

if (tmp.right != null) {

addAllLeft(tmp.right);

}

return returned;

}

}

/**

* Your BSTIterator will be called like this:

* BSTIterator i = new BSTIterator(root);

* while (i.hasNext()) v[f()] = i.next();

*/

}