leetcode 117. 填充每个节点的下一个右侧节点指针 II

117. 填充每个节点的下一个右侧节点指针 II

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        #层序遍历？
        if root is None:
            return root
        queue = deque()
        queue.append(root)
        result = []
        lastlayer = 1
        currentlayer = 0
        while queue:
            tmp = queue.popleft()
            result.append(tmp)
            if tmp.left is not None:
                queue.append(tmp.left)
                currentlayer+=1
            if tmp.right is not None:
                queue.append(tmp.right)
                currentlayer+=1
            lastlayer-=1
            if lastlayer==0:
                lastlayer=currentlayer
                currentlayer=0
                result.append(None)
        for i in range(len(result)):
            if result[i] is None:
                continue
            result[i].next=result[i+1]
        return root