BFS模板

BFS使用队列，将每个目前未搜索的结点依次入队，然后弹出队列首部元素进行遍历，一般有两个模板：

• 不需要确定当前遍历到了哪一层

  while (!queue.empty()) {
      cur = queue.front();
      queue.pop();
      for (node : adjacents_of(cur)) {
          if (node is valid && has not been accessed) {
              queue.push(node)
          }
      }
  }
  

  力扣中用到此模板的常见题目有：

  • 二叉树的最大深度

• 需要确定当前遍历到了哪一层

  int level = 0;
  while (!queue.empty()) {
      int size = queue.size();
      for (int i = 0; i < size; i++) {
          cur = queue.front();
          queue.pop();
          for (node : adjacents_of(cur)) {
              if (node is valid && has not been accessed) {
                  queue.push(node);
              }
          }
      }
      level++;
  }
  

  力扣中用到此模板的常见题目有：

  • 对称二叉树
  • 路径总和
  • 填充每个节点的下一个右侧节点指针
  • 填充每个节点的下一个右侧节点指针 II
  • 二叉树的所有路径
  • 二叉树的层序遍历
  • 二叉树的层次遍历 II
  • 相同的树