1
"""
2
# Definition for a Node.
3
class Node:
4
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
5
        self.val = val
6
        self.left = left
7
        self.right = right
8
        self.next = next
9
"""
10

11

12
class Solution:
13
    def connect(self, root: "Optional[Node]") -> "Optional[Node]":
14
        q = []
15
        q.append(root)
16
        if not root:
17
            return None
18
        while q:
19
            prev = None
20
            for i in range(len(q)):
21
                node = q.pop(0)
22
                if prev:
23
                    prev.next = node
24
                prev = node
25
                if node.left:
26
                    q.append(node.left)
27
                if node.right:
28
                    q.append(node.right)
29
            prev = None
30
        return root