日野弥生：勉強しよう
LeetCode 116 - 填充每个节点的下一个右侧节点指针
发表于2025年02月22日
本题由于next指针的前后关系，很容易想到使用广度优先搜索的思路进行层次遍历。但是层次遍历会随着二叉树深度的增加而指数增长，不符合题干要求。
转换思路，考虑先序遍历。先把根节点的左子树的next指针连向右子树。同时记录右子树的结点进入字典中。这里考虑用字典是键值可以存储树高，从而保证进入字典中的诸层级的右节点的next指针都能连接到同一层级的结点。
同时，从字典中查找和层级数相同的key是否存在，如果存在就从字典中删除该项并把该项的next连向left结点。
值得一提的是，用字典的好处不仅在于上述原因，还在于字典同一层级的键值对确实只有一个，毕竟如果从字典删除后马上就会把left的right送进字典。
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
def create_perfect_binary_tree(nums):
"""
创建一个包含给定数字的完美二叉树。
Args:
nums: 一个包含二叉树节点值的列表。
Returns:
完美二叉树的根节点。
"""
if not nums:
return None
# 计算树的深度
depth = 0
num_nodes = len(nums)
while (1 << (depth + 1)) - 1 < num_nodes:
depth += 1
def build_tree(index, level):
"""
递归构建二叉树。
Args:
index: 当前节点在列表 nums 中的索引。
level: 当前节点的深度。
Returns:
当前节点。
"""
if level > depth or index >= num_nodes:
return None
node = Node(nums[index])
node.left = build_tree(2 * index + 1, level + 1)
node.right = build_tree(2 * index + 2, level + 1)
return node
return build_tree(0, 0)
# 测试代码
nums = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
root = create_perfect_binary_tree(nums)
# 验证二叉树是否创建成功（可选）
def print_tree(node):
if node:
print(node.val)
if node.next:
print(node.val, node.next.val, sep="->")
print_tree(node.left)
print_tree(node.right)
class Solution:
# 字典存储结点和深度的键值对
q = {}
def connectIMPL(self, root: 'Optional[Node]', depth: int) -> 'Optional[Node]':
if root is None:
return None
# 由于是完美二叉树，所以左右子树要么同时没有，要么同时存在
if root.left and root.right:
# 左子节点的next指向右子结点
root.left.next = root.right
# 如果字典中有符合的结点，则连向左结点
if self.q:
item = self.q.get(depth+1)
if item:
lastRight = self.q.pop(depth + 1)
lastRight.next = root.left
# 继续往字典送进同级的右子节点
self.q[depth+1]=root.right
# 递归
self.connectIMPL(root.left, depth + 1)
self.connectIMPL(root.right, depth + 1)
return root
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
return self.connectIMPL(root, 0)
s = Solution()
s.connect(root)
print_tree(root)