AC simple Python solution with O(1) extra space, works for both Populating Next Right Pointer I and II


  • 1
    X

    Basically, I placed a dummy node before the head node of each level. Then I used two pointers "cur" and "ptr" respectively, to point to the node that's currently being explored and the one that's being linked to its right node. Below is my code.

    class Solution:
        # @param root, a tree node
        # @return nothing
        def connect(self, root):
            if root == None:
                return
            dummy = TreeNode(0)
            cur = root
            while cur != None:
                ptr = dummy
                dummy.next = None
                while cur != None:
                    if cur.left != None:
                        ptr.next = cur.left
                        ptr = ptr.next
                    if cur.right != None:
                        ptr.next = cur.right
                        ptr = ptr.next
                    cur = cur.next
                cur = dummy.next
            return

  • 0
    C

    Cool solution! Just couple of comments: None case is covered by the while loop so no need for special case; != None is not necessary.

    Below is almost the same code with those comments in mind:

    def connect(self, root):
        sentinel = TreeNode(0)
        head = root
        while head:
            current = sentinel
            sentinel.next = None
            while head:
                if head.left:
                    current.next = head.left
                    current = current.next
                if head.right:
                    current.next = head.right
                    current = current.next
                head = head.next
            head = sentinel.next 

Log in to reply
 

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