填充每个节点的下一个右侧节点指针

难度:

标签:

题目描述

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

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, 2¹² - 1] 范围内
-1000 <= node.val <= 1000

进阶：

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

代码结果

运行时间: 268 ms, 内存: 16.4 MB

/*
 * 思路：
 * 使用 Java Stream API 的 flatMap 处理树结构较为困难，
 * 因为 Stream 更适合处理列表而不是树状结构。尽管如此，
 * 我们依旧可以通过将每一层的节点放入列表，然后处理列表来实现连接。
 */
 
import java.util.*;
import java.util.stream.*;
 
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
 
    public Node() {}
 
    public Node(int val) {
        this.val = val;
    }
 
    public Node(int val, Node left, Node right, Node next) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.next = next;
    }
}
 
public class Solution {
    public void connect(Node root) {
        if (root == null) return;
        List<Node> levelNodes = Arrays.asList(root);
 
        while (!levelNodes.isEmpty()) {
            List<Node> nextLevel = new ArrayList<>();
            for (int i = 0; i < levelNodes.size(); i++) {
                Node current = levelNodes.get(i);
                if (i < levelNodes.size() - 1) {
                    current.next = levelNodes.get(i + 1);
                }
                if (current.left != null) nextLevel.add(current.left);
                if (current.right != null) nextLevel.add(current.right);
            }
            levelNodes = nextLevel;
        }
    }
}

解释

方法:

这个题解使用递归的方法来填充每个节点的 next 指针。主要思路是对于每一对左右子节点，先将它们的 next 指针相连。然后递归地处理左子节点的左右子树、右子节点的左右子树，以及跨越左右子节点连接它们右子树的最左节点和左子树的最右节点。

时间复杂度:

O(n)

空间复杂度:

O(log n)

代码细节讲解

🦆

题解中提到使用递归方法连接节点，这种方法在处理非完美二叉树时是否仍然有效，如果不有效，原因是什么？

▷

题解中使用的递归方法在处理非完美二叉树时依然有效。这是因为该方法主要依赖于父节点将其子节点连接起来，而不是假设所有层都完全填满。递归过程中，即使某些节点没有左子或右子，递归调用中对于null的检查将自动处理这些情况，不会执行无效操作。因此，该方法对于任何形式的二叉树都是适用的。

🦆

在递归函数`helper`的设计中，为何没有检查`n1`或`n2`的子节点是否存在就直接递归调用`helper(n1.left, n1.right)`和`helper(n2.left, n2.right)`？

▷

在`helper`函数的设计中，实际上有一个隐含的检查。因为`helper`函数的调用始于非空的根节点的左右子节点，并且只有当这些子节点非空时才会进一步递归调用其子树。如果`n1`或`n2`为null，递归会在调用点终止，不会进一步检查子节点。所以，尽管代码中没有显式检查每个子节点的存在性，但递归逻辑确保了只有存在的节点才会继续进行处理。

🦆

题解描述了一个递归连接`n1右子树的最左节点`与`n2左子树的最右节点`的逻辑，但具体如何实现这一步骤在代码中没有体现，能否详细解释这一逻辑的具体实现步骤？

▷

题解中确实提到连接`n1的右子树的最左节点`和`n2的左子树的最右节点`，这在代码中通过递归调用`helper(n1.right, n2.left)`实现。这一调用确保了n1的右子节点和n2的左子节点能够正确连接。由于递归的性质，这种连接会一直向下传递，直至叶节点。这里的关键是理解每次递归调用都是尝试连接两个相邻子树的最近边缘节点，最终形成完整的水平连接。

🦆

在题解的`helper`函数中，`n1.next = n2`这一操作是否会有重复执行的情况，如果有，这种重复对算法的性能有何影响？

▷

在`helper`函数中，`n1.next = n2`的操作确实可能被多次执行，尤其是在每个递归层级上对于同一对节点。然而，这种重复操作不会引入额外的性能开销，因为赋值操作是常数时间的操作。更重要的是，这种重复确保了算法的简洁性和正确性，无需引入复杂的状态检查。因此，虽然存在重复操作，但其对总体算法性能的影响可以忽略不计。

相关问题