Populating Next Right Pointers in Each Node

https://leetcode.com/explore/learn/card/data-structure-tree/133/conclusion/994/

BFS模板，level order traversal。值得注意的是目前解法

Time: O(n)

Space: O(n)

最优解不需要queue来维护level nodes

Time:O(n)

Space:O(1)

from collections import deque
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root == None:
            return
        q = deque([])
        q.append(root)
        while q:
            size = len(q)
            for i in range(size):
                curr = q.popleft()
                if i < size -1:
                    curr.next = q[0]
                if curr.left != None:
                    q.append(curr.left)
                if curr.right != None:
                    q.append(curr.right)
        return root
        

换做O(1)space的解法，主要是一下思想

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        node = root
        while node:
            #标记dummy node tmp来记录每一层最开始的位置
            curr = tmp = Node(-1)
            #每一个下一层的node连接我们都使用上一层的linkedlist也就是node
            while node:
                #这个node是上一层的node
                #如果左孩子存在，连！
                if node.left:
                    curr.next = node.left
                    curr = curr.next
                #如果右孩子存在，连！
                if node.right:
                    curr.next = node.right
                    curr = curr.next
                #上一层node去往上一层下一个node
                node = node.next
            #这层的linkedlist搭建好了，用tmp来表示当前层的linkedlist node又回到当前层的头指针来搭建下一层的linkedlist
            node = tmp.next
            
        return root