Populating Next Right Pointers in Each Node II

Problem Id: 117 Difficulty: Medium Tag: Tree Tag: Depth-first Search


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


# 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