C++使用队列实现二叉树的层序遍历（BFS广度优先搜索）

约定不等于承诺〃 2022-11-09 11:22 36阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70][]

**BFS 通常借助 队列 的先入先出特性来实现。**

算法流程：

*  特例处理： 当树的根节点为空，则直接返回空列表 \[\] ；
 *  初始化： 打印结果列表 res = \[\] ，包含根节点的队列 queue = \[root\] ；
 *  BFS 循环： 当队列 queue 为空时跳出；
 *  出队： 队首元素出队，记为 node；
 *  打印： 将 node.val 添加至列表 tmp 尾部；
 *  添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；
 *  返回值： 返回打印结果列表 res 即可。

vector<int> levelOrder(TreeNode* root) {
            //二叉树的层序遍历
            //使用BFS，广度优先搜索->queue
            queue<TreeNode*> q;//队列用于保存节点
            vector<int> res;//res为返回的数组
            //如果root不是空节点，将root放入队列
            if(root) q.push(root);
            //当队列为空时跳出循环
            while(!q.empty()){
                //先进先出，获取队首元素,并将其弹出
                TreeNode *temp = q.front();
                q.pop();
                //将当前节点的值压入
                res.push_back(temp->val);
                if(temp->left) q.push(temp->left);
                if(temp->right) q.push(temp->right);
            }
            return res;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1b2xhaWh1YTIwMTg_size_16_color_FFFFFF_t_70]: /images/20221023/80601f9788044a18acdb039e62698ed3.png