[LeetCode][117. Populating Next Right Pointers in Each Node II] 3 Approaches: BFS, BFS + LinkedList, Recursion

By Long Luo

This article is the solution 3 Approaches: BFS, BFS + LinkedList, Recursion of Problem 117. Populating Next Right Pointers in Each Node II.

Here shows 3 Approaches to slove this problem: BFS, BFS + LinkedList, Recursion.

BFS

Use BFS to level traversal, a List to store the Nodes of each level.

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

Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Node> levelNodes = new ArrayList<>();
for (int i = 0; i < size; i++) {
Node curNode = queue.poll();
levelNodes.add(curNode);
if (curNode.left != null) {
queue.add(curNode.left);
}
if (curNode.right != null) {
queue.add(curNode.right);
}
}

for (int i = 0; i < levelNodes.size() - 1; i++) {
Node node = levelNodes.get(i);
node.next = levelNodes.get(i + 1);
}
}

return root;
}

In fact, we just need a Node to store the Previous Node.

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

Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelCount = queue.size();
Node prev = null;
for (int i = 0; i < levelCount; i++) {
Node curNode = queue.poll();

if (prev != null) {
prev.next = curNode;
}

prev = curNode;

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

return root;
}

Analysis

  • Time Complexity: \(O(n)\).
  • Space Complexity: \(O(n)\).

BFS + LinkedList

Each level can be seem as a Linked List.

For example, the root node is a linked list with one node, and the second level is a linked list with two nodes and so on…

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

// the curNode as the linkedlist of each level
Node curNode = root;
while (curNode != null) {
// a dummyNode to travesal current Level
Node dummyNode = new Node(0);

// the prev Node of next level
Node prevNode = dummyNode;
while (curNode != null) {
if (curNode.left != null) {
// linked the left child
prevNode.next = curNode.left;
// update prev as LinkedList
prevNode = curNode.left;
}

if (curNode.right != null) {
prevNode.next = curNode.right;
prevNode = curNode.right;
}

// the next node of current level
curNode = curNode.next;
}

// after process the next level, process
curNode = dummyNode.next;
}

return root;
}

In fact, we just need a Node to store the Previous Node.

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
public static Node connect_bfs(Node root) {
if (root == null) {
return root;
}

Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelCount = queue.size();
Node prev = null;
for (int i = 0; i < levelCount; i++) {
Node curNode = queue.poll();

if (prev != null) {
prev.next = curNode;
}

prev = curNode;

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

return root;
}

Analysis

  • Time Complexity: \(O(n)\).
  • Space Complexity: \(O(1)\).

Recursion

It’s a little difficult but easy to get it.

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
public Node connect(Node root) {
if (root == null || (root.left == null && root.right == null)) {
return root;
}

if (root.left != null && root.right != null) {
root.left.next = root.right;
root.right.next = getNextHasChildrenNode(root);
}

if (root.left == null) {
root.right.next = getNextHasChildrenNode(root);
}

if (root.right == null) {
root.left.next = getNextHasChildrenNode(root);
}

// right should first
root.right = connect(root.right);
root.left = connect(root.left);

return root;
}

public Node getNextHasChildrenNode(Node root) {
while (root.next != null) {
if (root.next.left != null) {
return root.next.left;
}
if (root.next.right != null) {
return root.next.right;
}

root = root.next;
}

return null;
}

Analysis

  • Time Complexity: \(O(n)\).
  • Space Complexity: \(O(1)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗