使用c++求二叉树的最大宽度

在C++中，计算二叉树的最大宽度通常采用层序遍历（BFS，即广度优先搜索）的方法。这里提供一个基本步骤：

1. 定义一个队列（deque），用于存储当前层的所有节点，初始化时将根节点放入队列。
2. 初始化一个变量`width`记录当前层的节点数，以及一个变量`max_width`记录已找到的最大宽度，初始值均为1（因为至少有一层）。
3. 当队列非空时，循环进行以下操作：
a. 弹出队列头部元素，并将其左右子节点（如果有）加入队列。
b. 更新当前层的宽度，如果节点数大于`max_width`，则更新`max_width`。
4. 遍历完所有节点后，`max_width`即为二叉树的最大宽度。

以下是伪代码和简化版本的C++代码实现：

#include <iostream>
#include <queue>
using namespace std;

// 假设二叉树节点定义为 Node 类
struct Node {
    int val;
    Node* left;
    Node* right;
};

int maxDepth(Node* root) {
    if (root == nullptr) return 0;
    queue<Node*> q;
    q.push(root);
    int depth = 0, width = 1; // 初始深度为1，宽度为1
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            Node* node = q.front(); q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        width = max(width, size); // 更新宽度
        depth++;
    }
    return depth;
}

int main() {
    Node* root = ... // 填充二叉树节点
    int maxWidth = maxDepth(root);
    cout << "The maximum width of the binary tree is: " << maxWidth << endl;
    return 0;
}