Efficient BFS Python solution


  • 1
    S

    Uses a space = number of elements in a level ie when it works on level 3, a queue space of 4 nodes is required, so on and so forth. This is almost equal to the call stack space that will be consumed for storing function calls if recursively resolved.

    class Solution:
    
        def connect(self, root):
            if not root:
                return
            queue = []
            queue.append(root)
            queue.append(None)
            
            while queue:
                element = queue.pop(0)
                if element:
                    if queue[0]:
                        element.next = queue[0]
                    if element.left:
                        queue.append(element.left)
                        queue.append(element.right)
                else:
                    if queue:
                        queue.append(None)

  • 0
    D

    I would suggest you use deque and deque.popleft(). list.pop(0) takes O(n) time.


Log in to reply
 

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