BFS(宽度优先搜索)算法通用总结

Posted on |

宽度优先搜索在二叉树当中需要借助队列/栈等数据结构保存每一层的数据。有一个基本的模板可以参考，基本可以分为三个基本步骤：

  • 1.定义队列，这里可以是单向队列，双端队列或者栈。
  • 2.开始循环直到队列为空。
  • 3.从队列/栈中不断弹出元素进行处理。
  • 4.继续往队列/栈中添加下一级的非空节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void bfs(TreeNode root){
        //1.定义queue
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        //2.开始循环
        while (!queue.isEmpty()) {
            int currentSize = queue.size();
            //将当前队列的最上层的元素加入result
            result.add(((LinkedList<TreeNode>) queue).peekLast().val);
            for (int i = 0; i < currentSize; i++) {
                //3.从队列中弹出一个元素
                TreeNode treeNode = queue.poll();
								//4.继续添加元素
                if (treeNode.left != null) {
                    queue.offer(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.offer(treeNode.right);
                }
            }
        }
    }