116. Populating Next Right Pointers in Each Node

Populating Next Right Pointers in Each Node - LeetCodeLeetCode

层序遍历题，BFS解决。

唯一注意点是每层遍历完了才可以把下一层 push into queue.

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root: return None
        
        q = collections.deque([root])
        while q:
            width = len(q)
            nextLevel = []
            for _ in range(width):
                node = q.popleft()
                node.next = q[0] if q else None
                if node.left: nextLevel.append(node.left)
                if node.right: nextLevel.append(node.right)
            q.extend(nextLevel)
            
        return root