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.
1from collections import deque
2
3class Node:
4 def __init__(self, val=0, left=None, right=None, next=None):
5 self.val = val
6 self.left = left
7 self.right = right
8 self.next = next
9
10class Solution:
11 def connect(self, root: 'Node') -> 'Node':
12 if not root:
13 return None
14 queue = deque([root])
15 while queue:
16 size = len(queue)
17 prev = None
18 for i in range(size):
19 node = queue.popleft()
20 if prev:
21 prev.next = node
22 prev = node
23 if node.left:
24 queue.append(node.left)
25 if node.right:
26 queue.append(node.right)
27 return root
28Using the deque structure from Python's collections module, this solution effectively conducts a level-order traversal to set each node's next pointer. This is achieved by linking nodes within the same level.
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.