116. Populating Next Right Pointers in Each Node


This problem could be solved by BFS. We mark the level for each node, and for the node with the same level as previous one, the next field of previous node must be the current node.


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:
            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


  • Created: 2020-01-12 11:52:20

  • Last Motified: 2020-01-12 11:52:20

  • Tags: Tree, Depth-first Search