填充每个节点的下一个右侧节点指针
- 题目
- 题目描述
- 示例 1：
- 示例 2:
- 提示：
- 题解
- 方法：递归连接
- Python 实现
- 复杂度分析
- 提交结果
题目
题目描述
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例 1：
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，‘#’ 标志着每一层的结束。
示例 2:
输入：root = []
输出：[]
提示：
树中节点的数量在 [0, 212 - 1] 范围内
-1000 <= node.val <= 1000
进阶：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
题解
要解决这个问题，我们可以使用一个巧妙的方法来填充每个节点的 next 指针。由于题目要求只能使用常量级额外空间（不包括递归调用栈的空间），我们需要避免使用额外的数据结构如队列来进行层次遍历。这里提供一种基于递归的方法来实现这一目标。
方法：递归连接
我们可以通过递归的方式连接每一对相邻的节点。具体步骤如下：
-
基本情况：
- 如果当前节点为空或其左子节点为空（因为是完美二叉树，所以右子节点也为空），直接返回。
-
连接左右子节点：
- 对于每一个节点，将其左子节点的
next指向右子节点。
- 对于每一个节点，将其左子节点的
-
跨节点连接：
- 如果当前节点有
next节点，则将当前节点的右子节点的next指向当前节点的next节点的左子节点。
- 如果当前节点有
-
递归处理：
- 递归地对左右子树执行上述步骤。
这种方法利用了完美二叉树的特性，并且只使用了递归调用栈作为额外空间，符合题目的进阶要求。
Python 实现
首先定义二叉树节点的类 Node，然后编写递归函数来完成连接操作。
def connect(root: 'Node') -> 'Node':if not root or not root.left:return root# 连接左子节点到右子节点root.left.next = root.right# 如果当前节点有next节点，则连接当前节点的右子节点到下一个节点的左子节点if root.next:root.right.next = root.next.left# 递归连接左右子树connect(root.left)connect(root.right)return root
复杂度分析
- 时间复杂度：O(n)，其中 n 是树中节点的数量。每个节点都会被访问一次。
- 空间复杂度：O(1)，除了递归调用栈的空间外，没有使用额外的空间。对于完全平衡的树，递归调用栈的最大深度为 O(log n)。
这种方法利用了完美二叉树的结构特点，通过简单的递归实现了高效的连接操作。它不仅满足了题目对空间复杂度的要求，而且代码简洁易懂。
提交结果
