今日算法随笔：填充每个节点的下一个右侧节点指针 II

题目链接：117. 填充每个节点的下一个右侧节点指针 II

题目描述

给定一个二叉树，填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。

示例：

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：按层序遍历，'#' 表示每一层的末尾。

思路

层次遍历

这道题的核心是按层次遍历二叉树，并将每一层的节点通过 next 指针连接起来。由于树的结构不一定是完美二叉树，每个节点的左右子树数量可能不同，导致每层节点数量不均匀。因此，我们不能简单地直接使用完全二叉树的解法，而是需要根据当前节点的左右子节点来动态连接它们。

解题过程

方法运用

我们需要逐层遍历二叉树并构建 next 指针。在遍历时，使用以下几点策略：

1. 从左到右遍历当前层节点：

   • 对于每个节点，我们检查它是否有左子节点和右子节点。如果存在子节点，依次连接它们。

2. 使用 next 指针帮助跨节点连接：

   • 在跨越同一层不同父节点时（即当前节点的右子节点和下一个节点的左子节点），可以利用上一层已经构建好的 next 指针，来顺利访问该层的其他节点。

3. 构建下一层的连接关系：

   • 遍历当前层时，将下一层的节点依次连接起来，并通过虚拟节点 dummy 来指向下一层的第一个节点。

4. 遍历完一层后进入下一层：

   • 处理完当前层后，我们通过 dummy.next 找到下一层的第一个节点，然后继续处理这一层，直到所有层遍历完毕。

代码实现

下面是该算法的完整 Java 实现：

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        
        // 从当前层的头开始
        Node currentLevel = root;

        while (currentLevel != null) {
            Node dummy = new Node(0);  // 虚拟头节点，方便处理下一层的连接
            Node prev = dummy;  // 用来连接下一层节点的指针
            Node curr = currentLevel;  // 当前层的节点
            
            while (curr != null) {
                if (curr.left != null) {
                    prev.next = curr.left;
                    prev = prev.next;
                }
                if (curr.right != null) {
                    prev.next = curr.right;
                    prev = prev.next;
                }
                curr = curr.next;  // 移动到当前层的下一个节点
            }
            
            currentLevel = dummy.next;  // 进入下一层
        }
        
        return root;
    }
}

代码细节

1. Node 类：

   • Node 类代表二叉树的节点，每个节点包含 val（节点值），left（左子节点），right（右子节点）和 next（右侧节点的指针）。

2. 主逻辑：

   • currentLevel 变量用于追踪每一层的开始节点。
   • 通过 dummy 虚拟节点和 prev 指针将下一层的节点按顺序连接起来。
   • 遍历完当前层后，dummy.next 就会指向下一层的第一个节点，赋值给 currentLevel 以开始处理下一层。

3. 循环控制：

   • 内层 while (curr != null) 循环用于遍历当前层的所有节点，并连接它们的子节点。
   • 外层 while (currentLevel != null) 循环用于逐层处理，直到所有节点都完成连接。

常见问题解答

1. 为什么 currentLevel = dummy.next 能进入下一层？

dummy 是一个虚拟头节点，它用于帮助我们方便地连接当前层的子节点，即下一层的所有节点。当遍历当前层时，每次找到一个子节点，就把它连接到 dummy 的链表中（由 prev.next 来完成）。因此，dummy.next 最终会指向下一层的第一个节点。通过 currentLevel = dummy.next，我们就能顺利进入下一层的第一个节点，开始处理下一层。

2. 为什么需要 dummy 节点？

dummy 节点的作用是简化逻辑。在处理下一层节点时，我们需要将它们串起来，并且要记录下一层的第一个节点。使用 dummy 节点可以方便地处理这种情况，它始终指向下一层的开始位置，无需特殊处理第一个节点与其他节点的连接，简化了代码。

3. 该算法的时间和空间复杂度如何？

• 时间复杂度：O(n)，因为每个节点只会被访问一次。
• 空间复杂度：O(1)，除了递归栈之外，使用的额外空间是常数级别的。