题解36 | BFS#二叉树的最大宽度#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <algorithm>
#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int widthOfBinaryTree(TreeNode* root) {
        // write code here
        if(root == NULL) return 0;

        int res = 0,first,pose;

        queue<int> q;
        q.push(1);
        queue<TreeNode*> t;
        t.push(root);
        TreeNode *now;

        while (!q.empty()) {
            int len = q.size();
            for(int i = 0 ; i < len; i++){
                now = t.front();
                t.pop();

                pose = q.front();
                q.pop();

                if(i == 0)
                    first = pose;
                if(i == len-1)
                    res = std::max(res, pose - first + 1);

                if(now->left){
                    t.push(now->left);
                    q.push(pose*2);
                } 
                if(now->right){
                    t.push(now->right);
                    q.push(pose*2+1);
                }
            }

        }
        return res;
    }
};

算法基本思想

使用队列进行层次遍历二叉树，同时使用另一个队列记录每个节点的位置信息。

对于每一层的节点，计算出最左边节点和最右边节点的位置，然后计算宽度并更新最大宽度。

最后返回最大宽度。

具体步骤

该算法的详细步骤如下：

1. 初始化变量res为0，用于记录最大宽度。
2. 创建一个队列q和一个队列t，分别用于存储节点的位置信息和节点本身。
3. 将根节点的位置1入队q，将根节点入队t。
4. 进入循环，直到队列q为空。
5. 在每一轮循环中，先获取队列q的大小len，表示当前层的节点个数。
6. 遍历当前层的节点，从0到len-1。从队列t中取出一个节点now，从队列q中取出一个位置pose。
7. 如果当前节点是当前层的第一个节点（i == 0），则将pose赋值给first。
8. 如果当前节点是当前层的最后一个节点（i == len-1），则计算宽度（pose - first + 1）并更新res。
9. 如果当前节点有左子节点，则将左子节点入队t，位置pose*2入队q。
10. 如果当前节点有右子节点，则将右子节点入队t，位置pose*2+1入队q。
11. 返回res作为结果。

时间复杂度：

O(n)，其中n是二叉树的节点个数。需要遍历所有节点。

空间复杂度：

O(n)，其中n是二叉树的节点个数。需要使用队列和另一个队列分别存储节点和位置信息。