给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： 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)。

相关问题

题目给定一棵二叉树，计算该二叉树的深度、总节点个数和叶子节点个数。

好的，你可以将这些问题分开来回答。首先，计算一棵二叉树的深度可以使用递归算法，代码如下：

def depth(node):
    if node is None:
        return 0
    else:
        left_depth = depth(node.left)
        right_depth = depth(node.right)
        return max(left_depth, right_depth) + 1

其中，如果节点为空，则深度为0；否则，递归计算左子树和右子树的深度，然后返回左右子树深度的最大值再加上1。

接下来，计算二叉树的总节点个数同样可以使用递归算法，代码如下：

def count_nodes(node):
    if node is None:
        return 0
    else:
        left_count = count_nodes(node.left)
        right_count = count_nodes(node.right)
        return left_count + right_count + 1

其中，如果节点为空，则节点个数为0；否则，递归计算左子树和右子树的节点个数，然后返回左右子树节点个数之和再加上1。

最后，计算二叉树的叶子节点个数同样可以使用递归算法，代码如下：

def count_leaves(node):
    if node is None:
        return 0
    elif node.left is None and node.right is None:
        return 1
    else:
        left_count = count_leaves(node.left)
        right_count = count_leaves(node.right)
        return left_count + right_count

其中，如果节点为空，则叶子节点个数为0；如果节点的左右子树均为空，则该节点为叶子节点，叶子节点个数为1；否则，递归计算左子树和右子树的叶子节点个数，然后返回左右子树叶子节点个数之和。

希望这些算法对你有帮助，如有疑问请随时提出。

给定一个无环的二叉树根节点，根节点所在行号为1，往下子节点所在

行号依次加1，每个节点都有一个权值。现在有一个整数k，请你求出二叉树中第k行所有节点的权值之和。

算法思路：

我们可以使用递归来解决这个问题。对于每个节点，我们可以判断它是否在第k行，如果在第k行，就将它的权值加到答案中；否则，我们就递归处理它的左右子树，直到找到第k行的节点或者遍历完整棵树为止。

以下是Python代码实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def getSumOfKthLevel(self, root: TreeNode, k: int) -> int:
        if root is None:
            return 0
        if k == 1:
            return root.val
        return self.getSumOfKthLevel(root.left, k-1) + self.getSumOfKthLevel(root.right, k-1)

我们可以通过构造一棵测试树来验证上述代码的正确性：

# 构造一棵测试树
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 测试
s = Solution()
print(s.getSumOfKthLevel(root, 1)) # 输出: 1
print(s.getSumOfKthLevel(root, 2)) # 输出: 5
print(s.getSumOfKthLevel(root, 3)) # 输出: 13

以上代码输出的结果应该是：

1
5
13

这说明我们的代码是正确的。