小黑leetcode之旅: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 not root:
            return root
        # 层次遍历
        q = deque([root])
        while q:
            n = len(q)
            pre_node = None
            for i in range(n):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
                if i != 0:
                    pre_node.next = node
                pre_node = node
        return root

使用已建立的 next 指针

""" # 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 not root:
            return root
        # 生成孩子节点链表
        def handle(node):
            # 链表存在上一个节点
            if self.last:
                self.last.next = node
            # 不存在上一个节点，则赋予nextStart
            else:
                self.nextStart = node
            self.last = node 
        
        self.start = root
        while self.start:
            p = self.start
            # 重制nextStart、last
            self.nextStart = None
            self.last = None
            # 通过上一层链表生成孩子节点链表
            while p:
                if p.left:
                    handle(p.left)
                if p.right:
                    handle(p.right)
                p = p.next
            # 下一个链表开始
            self.start = self.nextStart
        return root