搜索系列之BFS

算法介绍

BFS（breadth-first search），广度优先搜索。与深度优先搜索不同的是，它是一层层进行遍历的，因此需要用先入先出的队列而非先入后出的栈进行遍历。

实现方式

基于队列

BFS就是一层一层的搜索

1. 先将根节点入队。
   
2. 判断队列是否为空，（若不为空）出队队首元素并访问之（刚开始就是根节点），再判断其有无左右孩子，若存在则将其加入到队尾。
   
3. 紧接着我们又出队队首元素，重复循环步骤 2。
   

跟 DFS 的栈实现非常相似，只不过将栈改成了队列而已。

我们依旧根据上节树节点数据结构的定义，写出二叉树的 BFS 遍历

树节点Node：

classNode{

 intval;

 NodelChild;  

 NoderChild;

   Node(intvalue){

       val=value;

   }

}

我们先创建一个队列：

Queue<Node>queue=newLinkedList<>();

首先将根节点root放入队列中：

queue.add(root);

当队列不为空时，出队队首元素...，下面贴出基于队列的完整代码：

classSolution{

 publicvoiddfs(BTreeroot){

       if(root==null) returnnull;

       Queue<Node>queue=newLinkedList<>();

       queue.add(root);

       while(!queue.isEmpty()){

           NodecurrNode=queue.poll();

           System.out.println(currNode.val);  

           if(currNode.lChild!=null){

             queue.add(currNode.lChild);  

           }

           if(currNode.rChild!=null){

               queue.add(currNode.rChild);

           }                  

       }

 }

}