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

it2024-12-09  17

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

给定一个二叉树

struct Node { int val; Node *left; Node *right; Node *next; }

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。

初始状态下,所有 next 指针都被设置为 NULL。

进阶:

你只能使用常量级额外空间。 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。

示例:

输入:root = [1,2,3,4,5,null,7] 输出:[1,#,2,3,#,4,5,7,#] 解释:给定二叉树如图 A所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。

提示:

树中的节点数小于 6000 -100 <= node.val <= 100

步骤:

利用BFS广度优先搜索的队列实现方法(很重要,可以背下来),从队列里面取出来的节点指向新的头结点,最后一个节点则指向空。 开始想了很久,看了其他人的题解后才发现指向新的头结点这个操作,还得多刷题。

""" # 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): if not root: return from collections import deque # 声明辅助队列,先将根节点入队 queue = deque() queue.append(root) # 遍历开始 while queue: # 先统计队列的大小 size = len(queue) # 开始逐层遍历 for i in range(size): # 节点出队 node = queue.popleft() # 记录当前节点的下一层节点 if node.left: queue.append(node.left) if node.right: queue.append(node.right) # 不是最后个节点时, # 让当前节点的 next 指针指向队列的头部节点 if i != size - 1: node.next = queue[0] return root
最新回复(0)