@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.
Actually, as mentioned in the comments above, it is possible to get the best of the two worlds in Java: allocate a sentinel, but only do it once and then reuse it. This makes the whole thing faster, makes life easier for the GC, and keeps the code as branch-free as possible.
Good answer, while the first BFS case can also be written as:
# BFS with queue
def connect(self, root):
if not root:
queue, nextLevel = [root],  # queue records the previous level
curr = queue.pop(0)
curr.next = queue
if not queue and nextLevel:
queue, nextLevel = nextLevel, queue
Could you please explain the space complexity to me?
I saw some posts talking about creating new node in each level causes O(1) space.
and there are log n levels, so the space complexity is O(log n)?
but I also find some people say algorithms like yours is space O(1)
Sure. firstNode is the dummy head of the next level, so firstNode.next will be the actual first node of next level. We use pre to record the previous node in next level and pre is initialized to firstNode.
Yes, I worked out the issue here. There are several border cases that I did not consider carefully.
How the tree look like in LeetCode, for this question, it has deliberate explanation under each question. I'm sure you can find the link.
I can give you the example here. For the input you mentioned, the tree should be
Explanation for 2nd solution: It's a BFS traversal inspired by aileengw. The curr pointer is the current level traveler and head is the left most element at next level and the tail is the right most element at next level till now. We move curr pointer at current level and populate the the next-link at its children level. (Here the gist is we can move curr to its next because this relationship was already populated in the previous round).