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.
1#include <iostream>
2#include <queue>
3using namespace std;
4
5struct Node {
6 int val;
7 Node *left;
8 Node *right;
9 Node *next;
10 Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
11};
12
13void connect(Node* root) {
14 if (!root) return;
15 queue<Node*> q;
16 q.push(root);
17 while (!q.empty()) {
18 int size = q.size();
19 Node* prev = NULL;
20 for (int i = 0; i < size; ++i) {
21 Node* node = q.front();
22 q.pop();
23 if (prev) prev->next = node;
24 prev = node;
25 if (node->left) q.push(node->left);
26 if (node->right) q.push(node->right);
27 }
28 // last node's next is already NULL since it was initialized
29 }
30}
31We use a queue to perform a level-order traversal. For each node processed on a level, we update its next pointer to point to the subsequent node. The last node in each level naturally points to NULL because of the initial constructor setup.
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.
This C approach uses an iterative strategy that does not require a queue. Instead, it uses head to signify the current level's starting node and a pair of pointers, nextHead and prev, to indicate the next level's starting point and moving connector.