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.
1function Node(val, left, right, next) {
2 this.val = val;
3 this.left = left;
4 this.right = right;
5 this.next = next;
6};
7
8var connect = function(root) {
9 if (!root) return null;
10 let queue = [];
11 queue.push(root);
12 while (queue.length) {
13 let size = queue.length;
14 let prev = null;
15 for (let i = 0; i < size; i++) {
16 let node = queue.shift();
17 if (prev) prev.next = node;
18 prev = node;
19 if (node.left) queue.push(node.left);
20 if (node.right) queue.push(node.right);
21 }
22 }
23 return root;
24};This JavaScript function organizes nodes in a level-order sequence using an array as a queue substitute. By adjusting the next pointers, it ensures each node links to the next right node correctly.
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.
using namespace std;
struct Node {
int val;
Node *left;
Node *right;
Node *next;
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
};
void connect(Node* root) {
if (!root) return;
Node* current = root;
Node dummy(0);
Node* tail = &dummy;
while (current) {
dummy.next = NULL;
tail = &dummy;
while (current) {
if (current->left) {
tail->next = current->left;
tail = tail->next;
}
if (current->right) {
tail->next = current->right;
tail = tail->next;
}
current = current->next;
}
current = dummy.next;
}
}
The C++ solution employs a dummy node to efficiently handle the connections of the next level. tail manages the connections, while current processes the current level. dummy aids resetting pointers at each step.