【五月集训】（第十七天）—— 广度优先遍历

• 解题报告
• • 开幕式焰火
  • 二叉树的层序遍历
  • 奇偶树
  • 推箱子

题目链接：LCP 44. 开幕式焰火

解题思路

哈希表记录颜色，队列存放每个节点扩展出来的节点，统计每个节点的颜色是否出现，没有出现则记录该颜色，颜色数量加1。

解题代码

class Solution {
public:
    int numColor(TreeNode* root) {
        int color[1010] = {0};
        int ans = 0;
        queue q;
        q.push(root);
        while(!q.empty()){
            TreeNode* now = q.front();
            q.pop();
            if(now -> right) q.push(now -> right);
            if(now -> left) q.push(now -> left);
            if(color[now -> val] == 0){
                color[now -> val] ++ ;
                ans ++ ;
            }
        }
        return ans;
    }
};

题目链接：102. 二叉树的层序遍历

解题思路

遍历的方法与上一题相同，这里的难点是将每一层分层。可以定义一个 currentSize 记录当前的队列大小，即当前层的数量。因为我们每一次往队列加入节点一定是下一层的节点，当我们一次遍历一层节点并出队，同时又会加入下一层的节点，当这层节点遍历完毕，队列中只会剩下下一层的节点了。

解题代码

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        vector> ans;
        queue q;
        q.push(root);
        if(!root){
            return ans;
        }
        while(!q.empty()){
            int currentSize = q.size();
            ans.push_back({});
            for(int i = 0; i < currentSize; i ++ ){
                TreeNode* now = q.front();
                q.pop();
                ans.back().push_back(now -> val);
                if(now -> left)
                    q.push(now -> left);
                if(now -> right)
                    q.push(now -> right);
            }
        }
        return ans;
    }
};

题目链接：1609. 奇偶树

解题思路

与上一题的分层思路相同，通过当前队列的大小记录每层的数量。遍历每一层时，只要在上一题的基础上加上对层数和元素的奇偶判断和大小判断。
可以用一个preValue记录上一个数字大小用来判断递增递减。

解题代码

class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        queue q;
        q.push(root);
        int layer = 0;
        while(!q.empty()){
            int currentSize = q.size();
            int preValue = layer & 1 ? INT_MAX : INT_MIN;
            for(int i = 0; i < currentSize; i ++ ){
                TreeNode* now = q.front();
                q.pop();
                if((now -> val & 1) == (layer & 1)){
                    return false;
                }
                if(((layer & 1) == 1 && now -> val >= preValue) || 
                    ((layer & 1) == 0 && now -> val <= preValue)){
                    return false;
                }
                preValue = now -> val;
                if(now -> left)
                    q.push(now -> left);
                if(now -> right)
                    q.push(now -> right);
            }
            layer ++ ;
        }
        return true;
    }
};

题目链接：1263. 推箱子

解题思路

解题代码