117. Populating Next Right Pointers in Each Node II


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.


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 12:08:14

  • Last Motified: 2020-01-12 12:08:14

  • Tags: Tree, Depth-first Search