"""

# Definition for a Node.

class Node:

    def __init__(self, val, left, right, next):

        self.val = val

        self.left = left

        self.right = right

        self.next = next

"""

class Solution:

    def connect(self, root: 'Node') -> 'Node':

        if not root:

            return

        stack = [root]

        #ans = []

        while stack:

            tem_stack=[]

            #tem_ans = []

            for i in stack:

                tem_ans.append(i.val)

                if i.left:

                    tem_stack.append(i.left)

                if i.right:

                    tem_stack.append(i.right)

            if len(tem_stack)>1:

                for i in range(len(tem_stack)-1):

                    tem_stack[i].next = tem_stack[i+1]

            stack = tem_stack

            #ans.append(tem_ans)

        return root

class Solution:

    def connect(self, root: 'Node') -> 'Node':

        cur = root

        head = None

        tail = None

        while cur:

            while cur:

                if cur.left:

                    if not head:

                        head = cur.left

                        tail = cur.left

                    else:

                        tail.next = cur.left

                        tail = tail.next

                if cur.right:

                    if not head:

                        head = cur.right

                        tail = cur.right

                    else:

                        tail.next = cur.right

                        tail = tail.next

                cur = cur.next

            cur = head

            head = None

            tail = None

        return root