1. question: 填充每一个节点的下一个右侧节点指针II（中等）
给定一个二叉树
1
2
3
4
5
6
| struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
|
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii
进阶：
1
2
| 你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
|
示例：
1
2
3
| 输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。
|
提示：
1
2
| 树中的节点数小于 6000
-100 <= node.val <= 100
|
2. answers
这道题和填充每一个节点的右侧节点指针类似，只不过这里是二叉树，而上一道题是满二叉树。思路是一样的，和层序遍历类似。注意，在测试的时候需要找到下一层的首节点。代码如下所示：
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
| public class Solution_0058 {
public static Nodess connect(Nodess root) {
Nodess head = root;
Queue<Nodess> queue = new LinkedList<>();
if(root != null) queue.offer(root);
int length;
Nodess index;
while(queue.size() > 0) {
length = queue.size();
index = queue.peek();
while(length-- > 0) {
root = queue.poll();
if(root != index) {
index.next = root;
index = index.next;
}
if(root.left != null) queue.offer(root.left);
if(root.right != null) queue.offer(root.right);
}
}
return head;
}
public static void main(String[] args) {
Nodess n7 = new Nodess(7);
Nodess n5 = new Nodess(5);
Nodess n4 = new Nodess(4);
Nodess n3 = new Nodess(3, null, n7, null);
Nodess n2 = new Nodess(2, n4, n5, null);
Nodess n1 = new Nodess(1, n2, n3, null);
Nodess result = connect(n1);
Queue<Nodess> queue = new LinkedList<>();
if(result != null) queue.offer(result);
while(queue.size() > 0) {
boolean tag = false;
result = queue.poll();
while(result != null) {
if(!tag) {
if(result.left != null) {
queue.offer(result.left);
tag = true;
} else if(result.right != null) {
queue.offer(result.right);
tag = true;
}
}
System.out.print(result.val + "\t");
result = result.next;
}
System.out.println("#");
}
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
