AC Python O(1) space solution 12 lines and easy to understand


  • 30

    The algorithm is a BFS or level order traversal. We go through the tree level by level. node is the pointer in the parent level, tail is the tail pointer in the child level.
    The parent level can be view as a singly linked list or queue, which we can traversal easily with a pointer.
    Connect the tail with every one of the possible nodes in child level, update it only if the connected node is not nil.
    Do this one level by one level. The whole thing is quite straightforward.

    Python

    def connect(self, node):
        tail = dummy = TreeLinkNode(0)
        while node:
            tail.next = node.left
            if tail.next:
                tail = tail.next
            tail.next = node.right
            if tail.next:
                tail = tail.next
            node = node.next
            if not node:
                tail = dummy
                node = dummy.next
    
    
    # 61 / 61 test cases passed.
    # Status: Accepted
    # Runtime: 100 ms
    # 95.26%

  • 0
    S

    @dietpepsi Elegant! Great use of dummy pointer. Thanks for the solution!


  • 0
    G

    Hi, thank you for sharing the code. I really have difficulty in understanding how the dummy works: it seems to me that dummy is a floating node all the time, and at the end of every level, node will become Null since it is assigned to dummy.next. Therefore, node will not pass the while condition for every level, actually it should get stuck for the 1st round (root node). I'm really struggling where I got wrong. Could you help to point out? Thank you so much!


  • 0
    S

    For the benefit of others, here is more intuitive code with more clear names to clarify their meaning and purpose. Whole credit is to @dietpepsi whose this post actually inspired me to think of linked list as a queue

    class Solution:
        # @param root, a tree link node
        # @return nothing
        def connect(self, root):
            if not root:
                return
    
            sentinel = rear = TreeLinkNode(0)
            # enqueue root
            front = root
            front.next = rear
    
            while front is not rear:
                # dequeue from front
                node  = front
                front = front.next
                # if sentinel is dequeued
                if node is sentinel:
                    # if rear has non sentinel items
                    # enqueue sentinel back
                    if rear is not sentinel:
                        rear.next = sentinel
                        rear = rear.next
                        continue
    
                if node.next is sentinel: # full level is traversed
                    node.next = None
    
                # enqueue left
                if node.left:
                    rear.next = node.left
                    rear = rear.next
                # enqueue right
                if node.right:
                    rear.next = node.right
                    rear = rear.next

  • 0
    M

    @gaosuwoniu The first line where we make tail and dummy equal to same tree node that we newly created.

    tail = dummy = TreeLinkNode(0)

    Afterwards in while loop, first line we make tail.next equal to node.left which is the left node (of the current node being traversed) in original tree. So if python assignment works the same as pointers in C, in this line essentially we are also setting dummy.next to node.left, because they are pointing towards same node.

    tail.next = node.left

    now in the last line of the function we are equating node = dummy.next which is pointing to node.left since we did not move it at all in the entire loop. That is how its going to the next level.


  • 2
    D
    My python solution
    def connect(self, root):
            while root:
                cur = tmp = TreeLinkNode(0)
                while root:
                    if root.left:
                        cur.next = root.left
                        cur = root.left
                    if root.right:
                        cur.next = root.right
                        cur = root.right
                    root = root.next
                root = tmp.next

Log in to reply
 

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