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

Commit3f0d0b1

Browse files
populating next right pointers in each node II
1 parent5f55afa commit3f0d0b1

File tree

2 files changed

+69
-0
lines changed

2 files changed

+69
-0
lines changed

‎Common/src/classes/TreeLinkNode.java

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

0 commit comments

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