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

Commit7332d36

Browse files
populating next right pointers in each node
1 parent3f0d0b1 commit7332d36

File tree

2 files changed

+62
-0
lines changed

2 files changed

+62
-0
lines changed
Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
packagemedium;
2+
importclasses.TreeLinkNode;
3+
4+
/**
5+
* Created by fishercoder1534 on 10/5/16.
6+
*/
7+
publicclassPopulatingNextRightPointersinEachNode {
8+
//copied this post: https://discuss.leetcode.com/topic/1106/o-1-space-o-n-complexity-iterative-solution
9+
//very clever and concise to make it in O(1) space
10+
11+
//based on level order traversal
12+
publicstaticvoidconnect(TreeLinkNoderoot) {
13+
14+
TreeLinkNodehead =null;//head of the next level
15+
TreeLinkNodeprev =null;//the leading node on the next level
16+
TreeLinkNodecur =root;//current node of current level
17+
18+
while (cur !=null) {
19+
20+
while (cur !=null) {//iterate on the current level
21+
//left child
22+
if (cur.left !=null) {
23+
if (prev !=null) {
24+
prev.next =cur.left;
25+
}else {
26+
head =cur.left;
27+
}
28+
prev =cur.left;
29+
}
30+
//right child
31+
if (cur.right !=null) {
32+
if (prev !=null) {
33+
prev.next =cur.right;
34+
}else {
35+
head =cur.right;
36+
}
37+
prev =cur.right;
38+
}
39+
//move to next node
40+
cur =cur.next;
41+
}
42+
43+
//move to next level
44+
cur =head;
45+
head =null;
46+
prev =null;
47+
}
48+
49+
}
50+
51+
publicstaticvoidmain(String...args){
52+
TreeLinkNoderoot =newTreeLinkNode(1);
53+
root.left =newTreeLinkNode(2);
54+
root.right =newTreeLinkNode(3);
55+
root.left.left =newTreeLinkNode(4);
56+
root.left.right =newTreeLinkNode(5);
57+
root.right.right =newTreeLinkNode(7);
58+
connect(root);
59+
}
60+
}

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,8 @@
88
|140|[Word Break II](https://leetcode.com/problems/word-break-ii/)|[Solution](../../blob/master/HARD/src/hard/WordBreakII.java)| ? |O(n^2) | Hard| Backtracking/DFS
99
|139|[Word Break](https://leetcode.com/problems/word-break/)|[Solution](../../blob/master/MEDIUM/src/medium/WordBreak.java)| O(n^2)|O(n) | Medium| DP
1010
|133|[Clone Graph](https://leetcode.com/problems/clone-graph/)|[Solution](../../blob/master/MEDIUM/src/medium/CloneGraph.java)| O(n)|O(n) | Medium| HashMap, BFS
11+
|117|[Populating Next Right Pointers in Each Node II](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/)|[Solution](../../blob/master/HARD/src/hard/PopulatingNextRightPointersinEachNodeII.java)| O(n)|O(1) | Hard| BFS
12+
|116|[Populating Next Right Pointers in Each Node](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)|[Solution](../../blob/master/MEDIUM/src/medium/PopulatingNextRightPointersinEachNode.java)| O(n)|O(1) | Medium| BFS
1113
|91|[Decode Ways](https://leetcode.com/problems/decode-ways/)|[Solution](../../blob/master/MEDIUM/src/medium/DecodeWays.java)| O(n)|O(n) | Medium| DP
1214
|76|[Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/)|[Solution](../../blob/master/HARD/src/hard/MinimumWindowSubstring.java)|O(n)|O(k)|Hard|Two Pointers
1315
|56|[Merge Intervals](https://leetcode.com/problems/merge-intervals/)|[Solution](../../blob/master/HARD/src/hard/MergeIntervals.java)|O(n*logn)|O(1)|Hard|

0 commit comments

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