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
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