This problem is almost the same as 116. We could solve this problem by BFS with one additional field level to mark the level of each node.
If the level of current node equals to the level of last visited node, then the next field should be pointed to current node.
# 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 from collections import deque class Solution: def connect(self, root: 'Node') -> 'Node': last = None last_level = -1 queue = deque([[root, 0]]) while queue: node, level = queue.popleft() if node is None: continue if last_level == level: last.next = node last, last_level = node, level queue.append([node.left, level + 1]) queue.append([node.right, level + 1]) return root