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

难度: Medium

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

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

进阶：

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

Submission

运行时间: 268 ms

内存: 16.4 MB

"""
# Definition for a Node.
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
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root is None:
            return

        def helper(n1, n2):
            if n1 is None or n2 is None:
                return

            n1.next = n2
            helper(n1.left, n1.right)
            helper(n2.left, n2.right)
            helper(n1.right, n2.left)

        helper(root.left, root.right)
        return root

Explain

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

时间复杂度: O(n)

空间复杂度: O(log n)

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root is None:
            return

        def helper(n1, n2):
            if n1 is None or n2 is None:
                return
            
            # 将一对节点的 next 指针相连
            n1.next = n2
            # 递归处理 n1 的左右子树 
            helper(n1.left, n1.right)
            # 递归处理 n2 的左右子树
            helper(n2.left, n2.right)
            # 连接 n1 右子树的最左节点和 n2 左子树的最右节点
            helper(n1.right, n2.left)
        
        helper(root.left, root.right)
        return root

Explore

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

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

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

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