作者介绍：10年大厂数据\经营分析经验，现任字节跳动数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python，欢迎探讨交流
欢迎加入社区：码上找工作
作者专栏每日更新：
题目描述
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树的定义如下：
class Node: def __init__(self, val=0, left=None, right=None, next=None): self.val = val self.left = left self.right = right self.next = next
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 None。
初始状态下，所有 next 指针都被设置为 None。
方法一：层序遍历（BFS）
解题步骤：
- 使用队列进行层序遍历。
- 对于每一层的节点，通过队列的长度来确定节点的数量。
- 遍历当前层的节点，将每个节点的
next指向队列中的下一个节点。 - 最后一个节点的
next指向None。
Python 代码示例
from collections import deque def connect(root): """ 使用层序遍历来填充每个节点的下一个右侧节点指针。 参数: root (Node): 完美二叉树的根节点。 返回: Node: 修改后的树的根节点。 """ # 如果根节点为空，则直接返回None if not root: return None # 初始化队列，并将根节点加入队列 queue = deque([root]) # 当队列不为空时，进行层序遍历 while queue: # 获取当前层的节点数量 size = len(queue) # 遍历当前层的每个节点 for i in range(size): # 从队列中取出一个节点 node = queue.popleft() # 如果不是当前层的最后一个节点，将当前节点的next指向队列中的下一个节点 if i < size - 1: node.next = queue[0] # 如果当前节点有左子节点，将左子节点加入队列 if node.left: queue.append(node.left) # 如果当前节点有右子节点，将右子节点加入队列 if node.right: queue.append(node.right) # 返回根节点 return root
方法一利用层序遍历（BFS）来填充每个节点的下一个右侧节点指针，下面通过 ASCII 图形来说明这个方法的工作过程。
考虑一个完美二叉树如下所示：
1 / \ 2 3 / \ / \ 4 5 6 7
算法图解
我们使用队列来按层级遍历这棵树，并设置每个节点的 next 指针。以下是各个步骤的图解说明：
初始状态
- 初始化队列以包含根节点。
队列: [1]
第一层处理
- 取出节点 1，发现它有左右子节点 2 和 3，将这两个节点加入队列。
队列: [2, 3] next指针连接: 1 -> None
- 设置节点 1 的
next指向None（因为它是第一层的唯一节点）。
第二层处理
- 取出节点 2，由于它不是队列中的最后一个节点，设置
next指向队列中的下一个节点（节点 3）。同时将节点 2 的子节点 4 和 5 加入队列。
队列: [3, 4, 5] next指针连接: 2 -> 3
- 取出节点 3，设置
next指向None（因为它是当前层的最后一个节点），将节点 3 的子节点 6 和 7 加入队列。
队列: [4, 5, 6, 7] next指针连接: 3 -> None
第三层处理
- 处理节点 4, 5, 6, 7 类似，按顺序设置
next指针：
队列: [5, 6, 7] next指针连接: 4 -> 5 队列: [6, 7] next指针连接: 5 -> 6 队列: [7] next指针连接: 6 -> 7 队列: [] next指针连接: 7 -> None
在每一步中，我们从队列中移除一个节点，如果该节点不是当前层的最后一个节点，则将其 next 指针设置指向队列中的下一个节点。这样，每一层的节点都通过 next 指针连成一条链。当处理完当前层的所有节点后，队列中就包含了下一层的所有节点，重复以上步骤直到队列为空。这样的遍历确保了每个节点的 next 指针正确地指向了其右侧的节点。
方法二：使用已建立的 next 指针
解题步骤：
- 从根节点开始，利用上一层的
next指针来遍历和链接当前层的节点。 - 对于每个节点，链接其左子节点到右子节点，右子节点到下一个节点的左子节点（如果存在）。
Python 代码示例
def connect(root): """ 利用已建立的 next 指针来填充每个节点的下一个右侧节点指针。 参数: root (Node): 完美二叉树的根节点。 返回: Node: 修改后的树的根节点。 """ # 如果根节点为空，则直接返回None if not root: return None # 初始化leftmost指针，这个指针始终指向每一层的最左侧节点 leftmost = root # 当左侧节点存在时，继续处理下一层 while leftmost.left: # 使用head指针遍历当前层的节点，head初始指向当前层的最左侧节点 head = leftmost while head: # 将当前节点的左子节点的next指向右子节点 head.left.next = head.right # 如果当前节点的next不为空，将右子节点的next指向当前节点next的左子节点 if head.next: head.right.next = head.next.left # 移动到当前层的下一个节点 head = head.next # 移动到下一层的最左侧节点 leftmost = leftmost.left # 返回根节点 return root
方法三：递归法
解题步骤：
- 递归地连接每个节点的左子节点到其右子节点。
- 连接相邻子树的右子节点到左子节点。
Python 代码示例
def connect(root): if not root or not root.left: return root root.left.next = root.right if root.next: root.right.next = root.next.left connect(root.left) connect(root.right) return root
方法四：使用额外的节点追踪下一层的开始
解题步骤：
- 使用一个额外的节点
dummy来追踪每一层的开始。 - 通过一个循环连接同一层的所有节点。
Python 代码示例
def connect(root): if not root: return None current = root while current: dummy = Node(0) tail = dummy while current: if current.left: tail.next = current.left tail = tail.next if current.right: tail.next = current.right tail = tail.next current = current.next current = dummy.next return root
方法五：迭代优化
解题步骤：
- 类似于方法二，但使用迭代而非递归。
- 遍历每一层，连接相应的节点。
Python 代码示例
def connect(root): if not root: return None node = root while node and node.left: next_level = node.left while node: node.left.next = node.right node.right.next = node.next.left if node.next else None node = node.next node = next_level return root
算法分析
- 时间复杂度：所有方法都需要遍历每个节点，因此时间复杂度为 O(N)，其中 N 是树中的节点数。
- 空间复杂度：
- 方法一：O(N)，需要额外的队列。
- 方法二至五：O(1)，只使用常数额外空间。
不同算法的优劣势对比
- 层序遍历（方法一）直观且易于理解，但需要额外的空间来存储队列。
- 使用已建立的 next 指针（方法二）是空间复杂度最优的解法，适合空间敏感的应用。
- 递归法（方法三）代码简洁，但在非尾递归的编译器上可能导致栈溢出。
- 使用额外节点（方法四）适合不熟悉指针操作的场景。
- 迭代优化（方法五）提供了一个折中的解决方案，空间复杂度低，且较易于理解。
应用示例
这些方法可以用在需要层级遍历但希望节约空间的场景，如实时数据处理、游戏编程中的场景管理，或任何需要快速访问同一层级节点的数据结构设计中。
欢迎关注微信公众号 数据分析螺丝钉
