给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next 指针都被设置为 NULL。 进阶： 你只能使用常量级额外空间。 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。 示例： 输入：root = [1,2,3,4,5,6,7] 输出：[1,#,2,3,#,4,5,6,7,#] 解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。 提示： 树中节点的数量少于 4096 -1000 <= node.val <= 1000

这道题可以使用层次遍历的方法来解决，但是需要O(n)的空间复杂度。进阶要求常量级额外空间，可以使用递归的方法来解决。

对于每个节点，其左子节点的next指针指向其右子节点，如果该节点有next节点，则其右子节点的next指针指向其next节点的左子节点。这个过程可以通过递归实现。

代码如下：

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return root
        
        if root.left:
            root.left.next = root.right
            if root.next:
                root.right.next = root.next.left
                
        self.connect(root.left)
        self.connect(root.right)
        
        return root

时间复杂度为O(n)，空间复杂度为O(1)。