Use deque (not constant space). O(n) time complexity in Python


  • 0
    A
    from collections import deque
    class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if not root:
            return
        root.next = None
        if not root.left:
            return
        
        q = deque()
        q.append(root.left)
        q.append(root.right)
        preNode = None
        power = 1
        count = 0
        
        while q:
            node = q.popleft()
            count += 1
            
            if preNode != None:
                preNode.next = node
                
            if count == 1 << power:
                node.next = None
                preNode = None
                count = 0
                power += 1
            else:
                preNode = node
                
            if node.left:
                q.append(node.left)
                q.append(node.right)

Log in to reply
 

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