二叉树的最大宽度是指二叉树所有层中结点个数的最大值。例如：下面二叉树的宽度为4. image.png 输入二叉树的完全前序序列建立一棵二叉树（上机作业2：二叉树的建立和遍历），编写算法计算并输出二叉树

在计算机科学中，给定一个二叉树的完全前序序列（即根节点-左子树-右子树的顺序），我们可以通过递归的方式来构造二叉树，并计算其最大宽度。这里是一个步骤：

1. **构建二叉树**:
- 完全前序序列的第一个元素是根节点。
- 用剩下的序列构建左子树，直到序列为空，这意味着到达了叶子节点或子树结束。
- 接着构建右子树。

2. **计算宽度**:
- 初始化两个变量：`width` 表示当前层的节点数，`max_width` 表示已知的最大宽度。
- 遍历二叉树的每一层，对于每个节点，如果它是左孩子，`width` 增加 1；如果是右孩子，`width` 减少 1。这样每次移动到下一层时，`width` 就会反映新层的节点数。
- 每次更新节点，都要检查 `width` 是否大于 `max_width`，如果是，则更新 `max_width`。
- 最后返回 `max_width` 作为二叉树的最大宽度。

**算法伪代码**:

def build_tree(preorder):
    # 完全前序分解
    root_val, *rest = preorder
    if not rest:
        return None

    # 创建根节点
    root = TreeNode(root_val)
    
    # 递归构建左右子树
    left_subtree_size = rest[:rest.index(None)]  # 找到左子树的结束位置
    right_subtree_size = len(rest) - left_subtree_size  # 右子树大小
    root.left = build_tree(rest[:left_subtree_size])
    root.right = build_tree(rest[left_subtree_size:])

    # 计算宽度
    def calculate_width(node, depth=0):
        nonlocal max_width
        if node is None:
            return 0

        left_width = calculate_width(node.left, depth + 1)
        right_width = calculate_width(node.right, depth + 1)

        width = max(left_width, right_width) + 1  # 节点加上当前层的1（自身）
        max_width = max(max_width, width)

        return width

    calculate_width(root)
    return root, max_width

**相关问题--:**
1. 在二叉树宽度的计算过程中，为什么要对每个节点的左右子树分别递归调用 `calculate_width` 函数？
2. 在完全前序序列中，如何确定根节点的左子树和右子树的起始位置？
3. 如果输入的完全前序序列为空，如何处理这种情况？