Python O(1) space solution with generator


  • 1

    It is common BSF but I use a generator getLinkedList to mock a linked list.

    With getLinkedList, we can treat the current level as a linked list although it is not linked yet. We only have to traverse the current level and link all the nodes in it.

    Python

    class Solution:
        # @param root, a tree link node
        # @return nothing
        def connect(self, root):
            head = root
            
            while head:
                next_head = None
                for node in Solution.getLinkedList(head):
                    if not next_head:
                        next_head = cur = node
                    else:
                        cur.next = cur = node
                head = next_head
                
        
        @staticmethod
        def getLinkedList(head):
            while head:
                for node in head.left, head.right:
                    if node:
                        yield node
                head = head.next
    
    # 61 / 61 test cases passed.
    # Status: Accepted
    # Runtime: 88 ms
    # 90.53%
    

Log in to reply
 

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