Simple BFS solution


  • -2
    A

    I saw a lot of elegant code, this BFS is just another idea.

    def connect(self, root):

        if root == None:
            return root
        q1 = collections.deque()
        q2 = collections.deque()
        q1.append(root)
        while q1:
            node = q1.popleft()
            if q1:
                node.next = q1[0]
            if node.left != None:
                q2.append(node.left)
            if node.right != None:
                q2.append(node.right)
            if not(q1):
                q1 = collections.deque(q2)
                q2.clear()

  • 0
    S

    Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.


  • 0
    Q

    this is not constant space as required since you are using queue.


  • -1
    D

    below is my code. I only used one quene :

    def connect_queue(self, root):
        quene = []
        if root == None:
            return 
        quene.append((0,root))
        fatherDeep = -1
        leftNode = None
        while quene != [] :
            currentDeep, node = quene.pop(0)
            if node.left != None:
                quene.append((currentDeep+1, node.left))
            if node.right != None:
                quene.append((currentDeep+1, node.right))
            if currentDeep != fatherDeep:
                fatherDeep = currentDeep
            else:
                leftNode.next = node
            leftNode = node

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.