Poison

117. Populating Next Right Pointers in Each Node II

BFS
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
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
}

Queue<Node> queue = new LinkedList<>();
queue.add(root);

while (!queue.isEmpty()) {
Node pre = null;
for (int i = queue.size(); i > 0; i--) {
Node node = queue.poll();
node.next = pre;
pre = node;

if (node.right != null) {
queue.add(node.right);
}
if (node.left != null) {
queue.add(node.left);
}
}
}

return root;
}
}
Iterate
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
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
}

Node leftmost = root;
while (leftmost != null) {
Node dummyHead = new Node();
Node pre = dummyHead;

Node node = leftmost;
while (node != null) {
if (node.left != null) {
pre.next = node.left;
pre = pre.next;
}
if (node.right != null) {
pre.next = node.right;
pre = pre.next;
}

node = node.next;
}

leftmost = dummyHead.next;
}

return root;
}
}
Reference

117. Populating Next Right Pointers in Each Node II