Sponsored
Sponsored
This approach uses a breadth-first search (BFS) strategy by employing a queue to keep track of nodes at the current level and connect their children nodes from left to right. After processing all nodes on a level, we move to the children (if any), ensuring the next pointers are correctly set.
Time Complexity: O(n), where n is the number of nodes in the tree since each node is enqueued and dequeued once.
Space Complexity: O(n) for the queue in the worst case where the last level of the tree has a maximum number of nodes.
1using System;
2using System.Collections.Generic;
3
4public class Node {
5 public int val;
6 public Node left;
7 public Node right;
8 public Node next;
9
10 public Node() {}
11
12 public Node(int _val) {
13 val = _val;
14 }
15
16 public Node(int _val, Node _left, Node _right, Node _next) {
17 val = _val;
18 left = _left;
19 right = _right;
20 next = _next;
21 }
22}
23
24public class Solution {
25 public void Connect(Node root) {
26 if (root == null) return;
27 Queue<Node> queue = new Queue<Node>();
28 queue.Enqueue(root);
29 while (queue.Count > 0) {
30 int size = queue.Count;
31 Node prev = null;
32 for (int i = 0; i < size; i++) {
33 Node node = queue.Dequeue();
34 if (prev != null) prev.next = node;
35 prev = node;
36 if (node.left != null) queue.Enqueue(node.left);
37 if (node.right != null) queue.Enqueue(node.right);
38 }
39 if (prev != null) prev.next = null;
40 }
41 }
42}
43The C# solution employs a queue to facilitate level-order traversal, dynamically linking each node's next pointer while processing each level of the tree.
This approach leverages a two-pointer or head-tail strategy to eliminate the need for extra storage space beyond two pointers. The idea is to work with two nested loops; an outer loop goes level by level, and an inner loop connects nodes within the same level by their next pointers.
Time Complexity: O(n) since each node is processed once.
Space Complexity: O(1), only utilizing a few pointers.
The Java version utilizes a dummy node and a tail pointer to establish the next pointers for nodes at the current level, moving forward to the following level through a loop-driven progression.