[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
29public 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
30public 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
30public 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
39public 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. 😉😃💗