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.


    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
               = cur = node
                head = next_head
        def getLinkedList(head):
            while head:
                for node in head.left, head.right:
                    if node:
                        yield node
                head =
    # 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.