A non-recursion and constant space cost AC solution


  • 0
    L

    The idea is very simple.
    Parent is the first node of current level, and during the while, visited each node of current level by parent=parent.next
    During each while, first visit the left child, if the right child is not None, then the parent.left.next=parent.right.
    Othervise, visited the parent next, and find the first child node that is not None.
    The next node of right child can be found in the same way.
    At the end, if parent.next is None, it means we have already find all the children's next node of current level. Then we should set first node of next level as parent for next while.

    class Solution:
        # @param root, a tree node
        # @return nothing
        def connect(self, root):
            next_start=[]
            parent=root
            while None != parent:
                if None != parent.left:
                    if len(next_start) == 0:
                        next_start=[parent.left]
                    if None != parent.right:
                        parent.left.next=parent.right
                    else:
                        parent_next=parent.next
                        tmp_next=None
                        while None != parent_next:
                            tmp_next=parent_next.left if None != parent_next.left else parent_next.right
                            if None != tmp_next:
                                break
                            parent_next=parent_next.next
                        parent.left.next=tmp_next
                if None != parent.right:
                    if len(next_start) == 0:
                        next_start=[parent.right]
                    parent_next=parent.next
                    tmp_next=None
                    while None != parent_next:
                        tmp_next=parent_next.left if None != parent_next.left else parent_next.right
                        if None != tmp_next:
                            break
                        parent_next=parent_next.next
                    parent.right.next=tmp_next
                parent=parent.next
                if None == parent and 0 < len(next_start):
                    parent=next_start[0]
                    next_start=[]
            return

Log in to reply
 

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