当前位置：网站首页>Leetcode中使用BFS解决二叉树相关题目的行动指南

Leetcode中使用BFS解决二叉树相关题目的行动指南

2022-07-20 16:47:00 【Bert.King】

历史从不支持那种仅凭善意就能迎来盛世的观点。

广度优先搜索

BFS的算法解题套路

掌握了BFS的模板，我们首先可以拿经典的102. 二叉树的层序遍历练手。
进一步的掌握Leetcode的相关题目。

1. 二叉树BFS的代码模板

我相信对于计算机专业相关的朋友，可能依稀记得BFS和DFS在数据结构中的《图》章节进行引入介绍的。
其实对于这两种遍历方式，真正需要我们关注的是：核心思想和使用场景。

这里仅仅介绍一下用于遍历二叉树的BFS模板，后面再深入讲解其它地方的使用：

//第一步: 要使用『队列』这种数据结构
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 这里需要注意判空

while(!queue.isEmpty()){
    
   int size = queue.size();
   // 注意这里采用while，有时候采用for()更加方便，随机应变
   while(size > 0){
    
    // 在这个while里面处理的就是每一层的逻辑
       TreeNode cur = queue.poll();
        // 这里进行相关逻辑处理(一般)
                
       if(cur.left != null){
    
           queue.offer(cur.left);
       }

       if(cur.right != null){
    
           queue.offer(cur.right);
       }

      size--;
   }
}