117. Populating Next Right Pointers in Each Node II

Intuition

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.

Solution

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

Information

  • Created: 2020-01-12 12:08:14

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

  • Tags: Tree, Depth-first Search