173. Binary Search Tree Iterator

  • 39.9%

https://leetcode.com/problems/binary-search-tree-iterator/#/description

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.


方法一:

我的代码实现:

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
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
stack<TreeNode*> mystack;
public:
BSTIterator(TreeNode *root) {
push_all(root);
}

/** @return whether we have a next smallest number */
bool hasNext() {
return !mystack.empty();
}

/** @return the next smallest number */
int next() {
TreeNode* cur = mystack.top();
mystack.pop();
// if(cur->right)
push_all(cur->right);
return cur->val;
}
private:
void push_all(TreeNode* node){
for(;node!=NULL; node=node->left)
mystack.push(node);
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

https://discuss.leetcode.com/topic/6575/my-solutions-in-3-languages-with-stack

My solutions in 3 languages with Stack

I use Stack to store directed left children from root.

When next() be called, I just pop one element and process its right child as new root.

The code is pretty straightforward.

So this can satisfy O(h) memory, hasNext() in O(1) time,

But next() is O(h) time.

I can’t find a solution that can satisfy both next() in O(1) time, space in O(h).

Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class BSTIterator {
private Stack<TreeNode> stack = new Stack<TreeNode>();

public BSTIterator(TreeNode root) {
pushAll(root);
}

/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}

/** @return the next smallest number */
public int next() {
TreeNode tmpNode = stack.pop();
pushAll(tmpNode.right);
return tmpNode.val;
}

private void pushAll(TreeNode node) {
for (; node != null; stack.push(node), node = node.left);
}
}

C++:

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
class BSTIterator {
stack<TreeNode *> myStack;
public:
BSTIterator(TreeNode *root) {
pushAll(root);
}

/** @return whether we have a next smallest number */
bool hasNext() {
return !myStack.empty();
}

/** @return the next smallest number */
int next() {
TreeNode *tmpNode = myStack.top();
myStack.pop();
pushAll(tmpNode->right);
return tmpNode->val;
}

private:
void pushAll(TreeNode *node) {
for (; node != NULL; myStack.push(node), node = node->left);
}
};

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class BSTIterator:
# @param root, a binary search tree's root node
def __init__(self, root):
self.stack = list()
self.pushAll(root)

# @return a boolean, whether we have a next smallest number
def hasNext(self):
return self.stack

# @return an integer, the next smallest number
def next(self):
tmpNode = self.stack.pop()
self.pushAll(tmpNode.right)
return tmpNode.val

def pushAll(self, node):
while node is not None:
self.stack.append(node)
node = node.left

https://discuss.leetcode.com/topic/12265/my-solution-in-c-in-average-o-1-time-and-uses-o-h-memory

My Solution in C++, in average O(1) time and uses O(h) memory

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
class BSTIterator {
private:
stack<TreeNode*> st;
public:
BSTIterator(TreeNode *root) {
find_left(root);
}

/** @return whether we have a next smallest number */
bool hasNext() {
if (st.empty())
return false;
return true;
}

/** @return the next smallest number */
int next() {
TreeNode* top = st.top();
st.pop();
if (top->right != NULL)
find_left(top->right);

return top->val;
}

/** put all the left child() of root */
void find_left(TreeNode* root)
{
TreeNode* p = root;
while (p != NULL)
{
st.push(p);
p = p->left;
}
}
};

https://discuss.leetcode.com/topic/8154/morris-traverse-solution

Morris traverse solution

Traverse a BST from the smallest to the largest, then i solve this question simply use the inorder traversal.
To implement a iterator means we should traverse the tree step by step, so just split the inorder traversal.

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
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
p = root;
}

/** @return whether we have a next smallest number */
bool hasNext() {
return p != NULL;
}

/** @return the next smallest number */
int next() {
TreeNode *tmp;
int ret;
while(p) {
if (p->left == NULL) {
ret = p->val;
p = p->right;
break;
}
else {
tmp = p->left;
while (tmp->right != NULL && tmp->right != p)
tmp = tmp->right;
if (tmp->right == NULL) {
tmp->right = p;
p = p->left;
}
else {
ret = p->val;
tmp->right = NULL;
p = p->right;
break;
}
}
}

return ret;
}

TreeNode *p;
};

https://discuss.leetcode.com/topic/24617/c-using-stack

C++. using stack.

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
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
private:
TreeNode *current = NULL;
stack<TreeNode*> s;
public:
BSTIterator(TreeNode *root) {
// initialize the current pointer
current = root;
}

/** @return whether we have a next smallest number */
bool hasNext() {
while(current){
s.push(current);
current = current->left;
}
if(s.empty()){
return false;
}
return true;
}

/** @return the next smallest number */
int next() {
TreeNode* node = s.top();
s.pop();
current = node->right;
return node->val;
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

The basic idea behind this solution is that we have to implement inorder iteratively but it will gets split into two functions i.e. hasNext and next.
hasNext() will push all the left elements and check and return accordingly if elements are in the stack.
next() will just pop() the top element from the stack and update the current pointer to right .
For this we are taking a stack and a current pointer.
But maybe I may be wrong in hasNext as the requirement of question is O(1) for hasNext() as well.

Open for comments.


https://discuss.leetcode.com/topic/6629/two-python-solutions-stack-and-generator

Two Python solutions, stack and generator

stack solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def __init__(self, root):
self.stack = []
while root:
self.stack.append(root)
root = root.left

# @return a boolean, whether we have a next smallest number
def hasNext(self):
return len(self.stack) > 0

# @return an integer, the next smallest number
def next(self):
node = self.stack.pop()
x = node.right
while x:
self.stack.append(x)
x = x.left
return node.val

generator solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def __init__(self, root):
self.last = root
while self.last and self.last.right:
self.last = self.last.right
self.current = None
self.g = self.iterate(root)

# @return a boolean, whether we have a next smallest number
def hasNext(self):
return self.current is not self.last

# @return an integer, the next smallest number
def next(self):
return next(self.g)

def iterate(self, node):
if node is None:
return
for x in self.iterate(node.left):
yield x
self.current = node
yield node.val
for x in self.iterate(node.right):
yield x
谢谢你,可爱的朋友。