Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb00d05c

Browse files
BST iterator
1 parent832d877 commitb00d05c

File tree

3 files changed

+99
-0
lines changed

3 files changed

+99
-0
lines changed

‎Common/src/utils/CommonUtils.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -140,4 +140,13 @@ public static void print(List<String> list) {
140140
System.out.println();
141141
}
142142

143+
publicstaticvoidprintIntegerList(List<List<Integer>>res) {
144+
for(List<Integer>list :res){
145+
for(inti :list){
146+
System.out.print(i +", ");
147+
}
148+
System.out.println();
149+
}
150+
}
151+
143152
}
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
packagemedium;
2+
3+
importjava.util.LinkedList;
4+
importjava.util.Queue;
5+
6+
importclasses.TreeNode;
7+
8+
/**173. Binary Search Tree Iterator QuestionEditorial Solution My Submissions
9+
Total Accepted: 56053
10+
Total Submissions: 154876
11+
Difficulty: Medium
12+
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
13+
14+
Calling next() will return the next smallest number in the BST.
15+
16+
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.*/
17+
publicclassBSTIterator_using_q {
18+
19+
privateQueue<Integer>q;
20+
21+
/**My natural idea is to use a queue to hold all elements in the BST, traverse it while constructing the iterator, although
22+
* this guarantees O(1) hasNext() and next() time, but it uses O(n) memory.*/
23+
//Cheers! Made it AC'ed at first shot! Praise the Lord! Practice does make perfect!
24+
//I created a new class to do it using Stack to meet O(h) memory: {@link medium.BSTIterator_using_stack}
25+
publicBSTIterator_using_q(TreeNoderoot) {
26+
q =newLinkedList<Integer>();
27+
if(root !=null)dfs(root,q);
28+
}
29+
30+
privatevoiddfs(TreeNoderoot,Queue<Integer>q) {
31+
if(root.left !=null)dfs(root.left,q);
32+
q.offer(root.val);
33+
if(root.right !=null)dfs(root.right,q);
34+
}
35+
36+
/** @return whether we have a next smallest number */
37+
publicbooleanhasNext() {
38+
return !q.isEmpty();
39+
}
40+
41+
/** @return the next smallest number */
42+
publicintnext() {
43+
returnq.poll();
44+
}
45+
}
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
packagemedium;
2+
3+
importjava.util.Stack;
4+
5+
importclasses.TreeNode;
6+
7+
/**173. Binary Search Tree Iterator QuestionEditorial Solution My Submissions
8+
Total Accepted: 56053
9+
Total Submissions: 154876
10+
Difficulty: Medium
11+
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
12+
13+
Calling next() will return the next smallest number in the BST.
14+
15+
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.*/
16+
publicclassBSTIterator_using_stack {
17+
/**This is a super cool/clever idea: use a stack to store all the current left nodes of the BST, when pop(), we
18+
* push all its right nodes into the stack if there are any.
19+
* This way, we use only O(h) memory for this iterator, this is a huge saving when the tree is huge
20+
* since h could be much smaller than n. Cheers!*/
21+
22+
privateStack<TreeNode>stack;
23+
24+
publicBSTIterator_using_stack(TreeNoderoot) {
25+
stack =newStack();
26+
pushToStack(root,stack);
27+
}
28+
29+
privatevoidpushToStack(TreeNoderoot,Stack<TreeNode>stack) {
30+
while(root !=null){
31+
stack.push(root);
32+
root =root.left;
33+
}
34+
}
35+
36+
publicbooleanhasNext() {
37+
return !stack.isEmpty();
38+
}
39+
40+
publicintnext() {
41+
TreeNodecurr =stack.pop();
42+
pushToStack(curr.right,stack);
43+
returncurr.val;
44+
}
45+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp