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

2020年9月28日 0 作者 折纸

题目描述

file

方法一

"""
# 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
"""
import queue
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        q = queue.Queue()
        q.put(root)
        while not q.empty():
            size = q.qsize()
            pre = None
            for i in range(size):
                cur = q.get()
                if cur.left:
                    q.put(cur.left)
                if cur.right:
                    q.put(cur.right)
                if i == size-1:
                    cur.next = None
                if pre:
                    pre.next = cur
                pre = cur
        return root

 

思路

  • 我真的好菜啊555555
  • BFS √
  • 流畅地写完 ×

tricks

  • size = q.qsize()获取当前层的节点个数
  • pre = None 后进入当前层循环(for i in range(size))
  • 进入当前层循环后 if pre; pre=cur