题目:
给定一个二叉树:
struct Node { int val; Node *left; Node *right; Node *next; }填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为
NULL
。初始状态下,所有 next 指针都被设置为
NULL
。来源:力扣(LeetCode)
链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
示例:
示例 1:
输入:root = [1,2,3,4,5,null,7]
输出:[1,#,2,3,#,4,5,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化输出按层序遍历顺序(由 next 指针连接),'#' 表示每层的末尾。
示例 2:输入:root = []
输出:[]文章来源:https://www.toymoban.com/news/detail-729445.html
解法:
BFS,出队的时候,同层结点一起出队,顺便连接。文章来源地址https://www.toymoban.com/news/detail-729445.html
代码:
""" # 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': queue = [root] while queue: length = len(queue) for index in range(length): cur = queue.pop(0) if cur: if cur.left: queue.append(cur.left) if cur.right: queue.append(cur.right) if index < length - 1: cur.next = queue[0] return root
到了这里,关于力扣:117. 填充每个节点的下一个右侧节点指针 II(Python3)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!