用二叉链表计算二叉树的最大宽度c++

在C++中，我们可以使用广度优先搜索（BFS）算法结合一个队列来计算给定二叉树的最大宽度。二叉链表是一种特殊的二叉树表示形式，其中每个节点包含指向左右子节点的指针，而不是常规的左孩子右孩子的结构。

以下是基本步骤：

1. 首先，创建一个宽度数组`width`来存储当前层的节点数，初始化宽度为0，然后用一个变量`max_width`记录已知的最大宽度。

2. 使用一个队列`queue`，将根节点放入并设置初始深度为0。

3. 进行迭代直到队列为空：
- 弹出队首节点，更新当前深度。
- 将当前节点的左右子节点（如果存在）添加到队列，并更新对应的宽度计数。
- 更新宽度数组，记录当前层的节点数。
- 如果当前层的宽度大于`max_width`，则更新`max_width`。

4. 最后，`max_width`就是二叉链表表示的二叉树的最大宽度。

#include <iostream>
#include <queue>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;

    std::queue<TreeNode*> queue;
    queue.push(root);
    int depth = 0, max_width = 0;
    std::vector<int> width(depth);

    while (!queue.empty()) {
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            TreeNode* node = queue.front();
            queue.pop();
            width[depth]++;

            if (node->left) queue.push(node->left);
            if (node->right) queue.push(node->right);
        }
        
        max_width = std::max(max_width, *std::max_element(width.begin(), width.end()));
        depth++;
    }

    return max_width;
}