[Algorithm][队列][宽搜BFS][N叉树的层序遍历][二叉树的锯齿形层序遍历][二叉树最大宽度][在每个树行中找最大值]详细讲解

1.N 叉树的层序遍历

1.题目链接

• N 叉树的层序遍历

2.算法思路详解

• 思路：层序遍历 + 多加一个变量记录每一层结点的个数

3.代码实现

vector<vector<int>> LevelOrder(Node* root) 
{
    vector<vector<int>> ret; // 记录最终结果
    queue<Node*> q; // 层序遍历需要的队列

    if(root == nullptr)
    {
        return ret;
    }

    q.push(root);
    while(q.size())
    {
        int sz = q.size(); // 提取本层元素个数
        vector<int> tmp; // 统计本层元素

        while(sz--)
        {
            Node* node = q.front();
            q.pop();

            tmp.push_back(node->val);

            // 将该结点下一层入队列
            for(auto& child : node->children)
            {
                if(child != nullptr)
                {
                    q.push(child);    
                }
            }
        }

        ret.push_back(tmp);
    }

    return ret;
}

2.二叉树的锯齿形层序遍历

1.题目链接

• 二叉树的锯齿形层序遍历

2.算法原理详解

• 思路：层序遍历 + 增加标记位来比标记需要逆序的层

3.代码实现

vector<vector<int>> ZigzagLevelOrder(TreeNode* root) 
{
    vector<vector<int>> ret;
    queue<TreeNode*> q;

    if(root == nullptr)
    {
        return ret;
    }

    q.push(root);
    bool rvs = false; // reverse
    while(q.size())
    {
        int sz = q.size(); // 本层元素个数
        vector<int> tmp; // 统计本层元素

        while(sz--)
        {
            TreeNode* node = q.front();
            q.pop();

            tmp.push_back(node->val);

            // 孩子节点入队列
            if(node->left)
            {
                q.push(node->left);    
            }

            if(node->right)
            {
                q.push(node->right);    
            }
        }

        if(rvs)
        {
            reverse(tmp.begin(), tmp.end());
        }
        rvs = !rvs;

        ret.push_back(tmp);
    }

    return ret;
}

3.二叉树最大宽度

1.题目链接

• 二叉树最大宽度

2.算法原理详解

• 思路一：用层序遍历硬来

  • 统计每⼀层的最⼤宽度，优先想到的就是利⽤层序遍历，把当前层的结点全部存在队列⾥⾯，利⽤队列的⻓度来计算每⼀层的宽度，统计出最⼤的宽度
  • 但是，由于空节点也是需要计算在内的，因此，可以选择将空节点也存在队列⾥面
  • 这个思路是正常会想到的思路，但是极端情况下，最左边⼀条⻓链，最右边⼀条⻓链，需要存⼏亿个空节点，会超过最⼤内存限制
    

• 思路二：用数组存储二叉树的方式，给结点编号 -> vector<pair<TreeNode*, int>>

  • 依旧是利⽤层序遍历，但是这⼀次队列⾥⾯不单单存结点信息，并且还存储当前结点如果在数组中存储所对应的下标
  • 这样计算每⼀层宽度的时候，⽆需考虑空节点，只需将当层结点的左右结点的下标相减再加1即可
    

• 细节：如果⼆叉树的层数非常极端，下标有可能溢出，且任何⼀种数据类型都存不下下标的值，但是此点对本题并不构成问题

  • 数据的存储是⼀个环形的结构
  • 题⽬说明，数据的范围在int这个类型的最⼤值的范围之内，因此不会超出⼀圈
  • 因此，如果是求差值的话，⽆需考虑溢出的情况
    • 因为哪怕溢出，差值还是在接受范围内的
  • 为了防止溢出，需要使用unsigned int
    

• 如何计算每个结点在树中的下标呢？

  • 根据root下标起点，分为两个情况
    

3.代码实现

int WidthOfBinaryTree(TreeNode* root) 
{
    vector<pair<TreeNode*, size_t>> q; // 用vector模拟queue
    q.push_back({root, 1});

    size_t ret = 0;        
    while(q.size())
    {
        auto& [x1, y1] = q[0]; // 队头
        auto& [x2, y2] = q.back(); // 队尾

        ret = max(ret, y2 - y1 + 1);

        // 将下一层入队列
        vector<pair<TreeNode*, size_t>> tmp;
        for(auto& [x, y] : q)
        {
            if(x->left)
            {
                tmp.push_back({x->left, 2 * y});
            }

            if(x->right)
            {
                tmp.push_back({x->right, 2 * y + 1});
            }
        }
        q = tmp; // 覆盖原队列，避免了队列的头删
    }

    return ret;
}

4.在每个树行中找最大值

1.题目链接

• 在每个树行中找最大值

2.算法原理详解

• 思路：层序遍历 + 统计每一层的最大值

3.代码实现

vector<int> LargestValues(TreeNode* root) 
{
    if(root == nullptr)
    {
        return {};
    }

    vector<int> ret;
    queue<TreeNode*> q;

    q.push(root);
    while(q.size())
    {
        int sz = q.size(), maxV = INT_MIN;
        while(sz--)
        {
            TreeNode* node = q.front();
            q.pop();

            maxV = max(maxV, node->val);

            // 将下一层入队列
            if(node->left)
            {
                q.push(node->left);
            }

            if(node->right)
            {
                q.push(node->right);
            }
        }

        ret.push_back(maxV);
    }

    return ret;
}