BFS Python Solution, not sure about constant extra space


  • 1
    Y
    class Solution:
        def connect(self, root):
            if not root:return
            queue=collections.deque([(root,1)])
            dic=collections.defaultdict(list)
            while queue:
                node,level=queue.popleft()
                if not node:
                    continue
                dic[level].append(node)
                if node.left:
                    queue.append((node.left,level+1))
                if root.right:
                    queue.append((node.right,level+1))
            for key,nodes in dic.items():
                for i in range(len(nodes)-1):
                    dic[key][i].next=dic[key][i+1]
                    i+=1
                    dic[key][i].next=None
    

  • 0
    D

    @YangFan Very solid and clear solution. Great use of BFS here!


Log in to reply
 

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