The algorithm is a BFS or level order traversal. We go through the tree level by level. node is the pointer in the parent level, tail is the tail pointer in the child level.
The parent level can be view as a singly linked list or queue, which we can traversal easily with a pointer.
Connect the tail with every one of the possible nodes in child level, update it only if the connected node is not nil.
Do this one level by one level. The whole thing is quite straightforward.
def connect(self, node): tail = dummy = TreeLinkNode(0) while node: tail.next = node.left if tail.next: tail = tail.next tail.next = node.right if tail.next: tail = tail.next node = node.next if not node: tail = dummy node = dummy.next # 61 / 61 test cases passed. # Status: Accepted # Runtime: 100 ms # 95.26%
@dietpepsi Elegant! Great use of dummy pointer. Thanks for the solution!
Hi, thank you for sharing the code. I really have difficulty in understanding how the dummy works: it seems to me that dummy is a floating node all the time, and at the end of every level, node will become Null since it is assigned to dummy.next. Therefore, node will not pass the while condition for every level, actually it should get stuck for the 1st round (root node). I'm really struggling where I got wrong. Could you help to point out? Thank you so much!
For the benefit of others, here is more intuitive code with more clear names to clarify their meaning and purpose. Whole credit is to @dietpepsi whose this post actually inspired me to think of linked list as a queue
class Solution: # @param root, a tree link node # @return nothing def connect(self, root): if not root: return sentinel = rear = TreeLinkNode(0) # enqueue root front = root front.next = rear while front is not rear: # dequeue from front node = front front = front.next # if sentinel is dequeued if node is sentinel: # if rear has non sentinel items # enqueue sentinel back if rear is not sentinel: rear.next = sentinel rear = rear.next continue if node.next is sentinel: # full level is traversed node.next = None # enqueue left if node.left: rear.next = node.left rear = rear.next # enqueue right if node.right: rear.next = node.right rear = rear.next
@gaosuwoniu The first line where we make tail and dummy equal to same tree node that we newly created.
tail = dummy = TreeLinkNode(0)
Afterwards in while loop, first line we make tail.next equal to node.left which is the left node (of the current node being traversed) in original tree. So if python assignment works the same as pointers in C, in this line essentially we are also setting dummy.next to node.left, because they are pointing towards same node.
tail.next = node.left
now in the last line of the function we are equating node = dummy.next which is pointing to node.left since we did not move it at all in the entire loop. That is how its going to the next level.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.