Just convert common BFS solution to O(1) space, a simple python code


  • 12
    T

    common BFS

    class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        if not root:
            return
        queue, level = collections.deque([root]), collections.deque()
        while queue:
            node = queue.popleft()
            if node.left:
                level.append(node.left)
            if node.right:
                level.append(node.right)
            node.next = queue[0] if queue else None
            if not queue and level:
                queue, level = level, queue
    

    O(1) space

    class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        queue, level, curr = root, None, None
        while queue:
            if queue.left:
                if not level:
                    level = curr = queue.left
                else:
                    curr.next = queue.left
                    curr = curr.next
            if queue.right:
                if not level:
                    level = curr = queue.right
                else:
                    curr.next = queue.right
                    curr = curr.next
            queue = queue.next
            if not queue and level:
                queue, level, curr = level, None, None
    

    Use a fake head can save a few lines


  • 2
    C

    Good answer, while the first BFS case can also be written as:

    # BFS with queue
    def connect(self, root):
        if not root:
            return 
        queue, nextLevel = [root], []   # queue records the previous level
        while queue:
            curr = queue.pop(0)
            if curr.left:
                nextLevel.append(curr.left)
            if curr.right:
                nextLevel.append(curr.right)
            if queue:
                curr.next = queue[0]
            if not queue and nextLevel:
                queue, nextLevel = nextLevel, queue

Log in to reply
 

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