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.
This solution utilizes a queue to maintain the nodes at the current level. As nodes are processed, their children are enqueued, ensuring a level-order sequence of connections. Each node's next is set to the next node in the queue.
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.
1class Node {
2 public int val;
3 public Node left;
4 public Node right;
5 public Node next;
6
7 public Node() {}
8
9 public Node(int _val, Node _left, Node _right, Node _next) {
10 val = _val;
11 left = _left;
12 right = _right;
13 next = _next;
14 }
15}
16
17class Solution {
18 public void connect(Node root) {
19 Node current = root;
20 Node head = new Node(0);
21 while (current != null) {
22 Node tail = head;
23 head.next = null;
24 while (current != null) {
25 if (current.left != null) {
26 tail.next = current.left;
27 tail = tail.next;
28 }
29 if (current.right != null) {
30 tail.next = current.right;
31 tail = tail.next;
32 }
33 current = current.next;
34 }
35 current = head.next;
36 }
37 }
38}
39The 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.