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

Commit0618f12

Browse files
author
applewjg
committed
PopulatingNextRightPointersinEachNode
Change-Id: Ifc5dbb3901954dd5d95be941737865e5a65f360c
1 parentb9b46bc commit0618f12

File tree

2 files changed

+123
-0
lines changed

2 files changed

+123
-0
lines changed
Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
/*
2+
Author: King, higuige@gmail.com
3+
Date: Oct 7, 2014
4+
Problem: Populating Next Right Pointers in Each Node
5+
Difficulty: Easy
6+
Source: http://leetcode.com/onlinejudge#question_116
7+
Notes:
8+
Given a binary tree
9+
struct TreeLinkNode {
10+
TreeLinkNode *left;
11+
TreeLinkNode *right;
12+
TreeLinkNode *next;
13+
}
14+
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
15+
Initially, all next pointers are set to NULL.
16+
Note:
17+
You may only use constant extra space.
18+
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
19+
For example,
20+
Given the following perfect binary tree,
21+
1
22+
/ \
23+
2 3
24+
/ \ / \
25+
4 5 6 7
26+
After calling your function, the tree should look like:
27+
1 -> NULL
28+
/ \
29+
2 -> 3 -> NULL
30+
/ \ / \
31+
4->5->6->7 -> NULL
32+
33+
Solution: 1. Iterative: Two 'while' loops.
34+
2. Iterative: Queue. Use extra space.
35+
3. Recursive: DFS. Defect: Use extra stack space for recursion.
36+
*/
37+
38+
/**
39+
* Definition for binary tree with next pointer.
40+
* public class TreeLinkNode {
41+
* int val;
42+
* TreeLinkNode left, right, next;
43+
* TreeLinkNode(int x) { val = x; }
44+
* }
45+
*/
46+
publicclassSolution {
47+
publicvoidconnect(TreeLinkNoderoot) {
48+
if (root ==null)return;
49+
TreeLinkNodedummy =newTreeLinkNode(-1);
50+
TreeLinkNodepre =dummy;
51+
TreeLinkNodecur =root;
52+
while (cur !=null) {
53+
if (cur.left !=null) {
54+
pre.next =cur.left;
55+
pre =pre.next;
56+
}
57+
if (cur.right !=null) {
58+
pre.next =cur.right;
59+
pre =pre.next;
60+
}
61+
cur =cur.next;
62+
}
63+
connect(dummy.next);
64+
}
65+
}
Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
/*
2+
Author: King, wangjingui@gmail.com
3+
Date: Oct 7, 2014
4+
Problem: Populating Next Right Pointers in Each Node II
5+
Difficulty: Easy
6+
Source: https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
7+
Notes:
8+
Follow up for problem "Populating Next Right Pointers in Each Node".
9+
What if the given tree could be any binary tree? Would your previous solution still work?
10+
Note:
11+
You may only use constant extra space.
12+
For example,
13+
Given the following binary tree,
14+
1
15+
/ \
16+
2 3
17+
/ \ \
18+
4 5 7
19+
After calling your function, the tree should look like:
20+
1 -> NULL
21+
/ \
22+
2 -> 3 -> NULL
23+
/ \ \
24+
4-> 5 -> 7 -> NULL
25+
26+
Solution: 1. iterative way with CONSTANT extra space.
27+
2. iterative way + queue. Contributed by SUN Mian(孙冕).
28+
3. recursive solution.
29+
*/
30+
31+
/**
32+
* Definition for binary tree with next pointer.
33+
* public class TreeLinkNode {
34+
* int val;
35+
* TreeLinkNode left, right, next;
36+
* TreeLinkNode(int x) { val = x; }
37+
* }
38+
*/
39+
publicclassSolution {
40+
publicvoidconnect(TreeLinkNoderoot) {
41+
if (root ==null)return;
42+
TreeLinkNodedummy =newTreeLinkNode(-1);
43+
TreeLinkNodepre =dummy;
44+
TreeLinkNodecur =root;
45+
while (cur !=null) {
46+
if (cur.left !=null) {
47+
pre.next =cur.left;
48+
pre =pre.next;
49+
}
50+
if (cur.right !=null) {
51+
pre.next =cur.right;
52+
pre =pre.next;
53+
}
54+
cur =cur.next;
55+
}
56+
connect(dummy.next);
57+
}
58+
}

0 commit comments

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