Dare2Solve
The problem can be visualized as connecting all nodes on the same level from left to right. A level-order traversal (or breadth-first traversal) is suitable for this purpose, as it processes nodes level by level. By maintaining the order of nodes in each level, we can easily set the next
pointer for each node.
None
, return None
.next
pointer to the next node in the queue, or None
if it is the last node in the level.O(n)
, where n
is the number of nodes in the tree. Each node is processed once.
O(n)
in the worst case, where the queue might contain all nodes in the last level of the tree.
class Solution {
public:
Node* connect(Node* root) {
if (!root) return nullptr;
std::queue<Node*> queue;
queue.push(root);
while (!queue.empty()) {
std::queue<Node*> newQueue;
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node* node = queue.front();
queue.pop();
if (node) {
if (node->left) newQueue.push(node->left);
if (node->right) newQueue.push(node->right);
node->next = (i < size - 1) ? queue.front() : nullptr;
}
}
queue = newQueue;
}
return root;
}
};
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
class Solution:
def connect(self, root: 'Node') -> 'Node':
if not root:
return None
queue = [root]
while queue:
next_level = []
for i in range(len(queue)):
node = queue[i]
if i < len(queue) - 1:
node.next = queue[i + 1]
if node.left:
next_level.append(node.left)
if node.right:
next_level.append(node.right)
queue = next_level
return root
class Solution {
public Node connect(Node root) {
if (root == null) return null;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
if (i < size - 1) {
node.next = queue.peek();
}
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
}
return root;
}
}
var connect = function(root)
{
let queue = [];
queue.push(root);
while (queue.length)
{
let newQueue = [];
for (let i = 0; i < queue.length; i++) {
let node = queue[i];
if (node) {
if (node.left) newQueue.push(node.left);
if (node.right) newQueue.push(node.right);
node.next = queue[i+1] || null;
}
}
queue = newQueue;
}
return root;
};