@zhangshv123 TreeLinkNode tempChild = new TreeLinkNode(0); this is a temporary node.TreeLinkNode currentChild = tempChild; here currentChild points to temporary node. currentChild.next = root.left after this line currentChild has made tempChild next to point to root's left which is effectively one level below the root. That is where we want to go after first iteration, to the next level so after the while root = tempChild.next; is done so that root points to next level beg now.
@PeterP I didn't write the code, but from my understanding, the point of that is to move pre back to dummyHead in order to get ready for the next level (or not if there is no more level). Basically you move pre back to dummyHead and you move root to dummyHead.next (which is the left most of the current level), so that when you go back to the beginning of the while loop, pre will go to the most left node of the next level (root.left).
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.
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).
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