O(1) space, simple solution in python


  • -1
    class Solution(object):
        def connect(self, root):
            if not (root and (root.left or root.right)):
                return
    
            if root.left and root.right:
                root.left.next = root.right
    
            next = root.next
            while next and not (next.left or next.right):
                next = next.next
    
            if next:
                (root.right or root.left).next = next.left or next.right
    
            map(self.connect, (root.right, root.left))

  • 0
    A

    Can you explain why the connect function needs to be called on root.right before root.left in the last line?


  • 0

    Because the order is from left to right, so we should make the right part prepared before we connect the left part.

    Take bellow as example, if we connect left before right, then 7 will not connect to 8. You can
    execute it in hart and you will find it.

            1
           /  \
         2     3
        / \      \
       4  5       6
     /              \
    7                8

Log in to reply
 

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