Short python solution with O(n) time and O(1) space


  • 1
    H

    The main idea is to use a generator function childrenGen to generate all nodes for the current level, one by one, from left to right. Every time a new node is generated, we connect the current node to the new node, and call the new node current, until the current level is done. Then we use the leftmost node to seed the generator for the next level. Using generating function guarantees O(1) space at the same time simplifies the logic.

    class Solution:
        # @param root, a tree node
        # @return nothing
        def connect(self, root):
            genChild = self.childrenGen(root) # the generator seeded by the leftmost node of the parent level
            first = genChild.next() # the leftmost node at the current level
            while first:
                node = first
                while node:
                    node.next = node = genChild.next()
                genChild = self.childrenGen(first)
                first = genChild.next()
        def childrenGen(self, p):
            while p:
                if p.left: yield p.left
                if p.right: yield p.right
                p = p.next
            yield None
            return

Log in to reply
 

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