求输出二叉树的宽度的python代码

下面是输出二叉树宽度的Python代码：

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

def width(root):
    if not root:
        return 0
    
    max_width = 0
    level = [(root, 0)]
    
    while level:
        cur_level_width = level[-1][1] - level[0][1] + 1
        max_width = max(max_width, cur_level_width)
        next_level = []
        for node, pos in level:
            if node.left:
                next_level.append((node.left, pos * 2))
            if node.right:
                next_level.append((node.right, pos * 2 + 1))
        level = next_level
    
    return max_width

# 测试代码
root = Node(1, Node(3, Node(5), Node(3)), Node(2, None, Node(9)))
print(width(root))  # 输出 4

解释：

- `width` 函数接受一个二叉树的根节点 `root`，返回二叉树的宽度。
- 首先判断树是否为空，若为空，则返回 0。
- 定义最大宽度 `max_width` 为 0，定义一个列表 `level`，当前层的节点和它们的位置信息 `(node, pos)` 存储在该列表中，初始时，`level` 中只有根节点 `root` 和它的位置 0。
- 进入循环，判断当前层的宽度 `cur_level_width` 并更新最大宽度 `max_width`。
- 定义一个空列表 `next_level`，遍历 `level` 中的所有节点，对于每个节点，如果它有左子节点，则将左子节点和它的位置信息 `(node.left, pos * 2)` 存储到 `next_level` 中；如果它有右子节点，则将右子节点和它的位置信息 `(node.right, pos * 2 + 1)` 存储到 `next_level` 中。
- 更新 `level` 为 `next_level`，继续循环。
- 循环结束后，返回最大宽度 `max_width`。