19-line Python beats 100%


  • 0

    This is acutally a BFS using the extra pointer on the parent level.
    We find the start node in the next level while we connect the nodes in next level.

    class Solution(object):
        def connect(self, root):
            """
            :type root: TreeLinkNode
            :rtype: nothing
            """
            next, pre = None, None
            p = root
            while p:
                if p.left:
                    if not next:
                        next = p.left
                    if pre:
                        pre.next = p.left
                    pre = p.left
                if p.right:
                    if not next:
                        next = p.right
                    if pre:
                        pre.next = p.right
                    pre = p.right
                if not p.next:
                    p = next
                    pre = next = None
                else:
                    p = p.next         
    

    An even shorter version but it's much slower.

            next = pre = None
            p = root
            while p:
                if p.left:
                    if pre:
                        pre.next = p.left
                    pre = p.left
                if p.right:
                    if pre:
                        pre.next = p.right
                    pre = p.right
                next = next or p.left or p.right
                if not p.next:
                    p = next
                    pre = next = None
                else:
                    p = p.next
    

Log in to reply
 

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