Breadth First Search，广度优先搜索。
一般用于找最短路径，时间复杂度较低，代价是空间复杂度高。

框架

想象为一棵树从根节点到全部第二节点再到全部第三节点最后到全部根节点遍历。

  1. // 计算从起点 start 到终点 target 的最近距离
  2. int BFS(Node start, Node target) {
  3.     Queue<Node> q; // 核心数据结构
  4.     Set<Node> visited; // 避免走回头路
  6.     q.offer(start); // 将起点加入队列
  7.     visited.add(start);
  8.     int step = 0; // 记录扩散的步数
  10.     while (q not empty) {
  11.         int sz = q.size();
  12.         /* 将当前队列中的所有节点向四周扩散 */
  13.         for (int i = 0; i < sz; i++) {
  14.             Node cur = q.poll();
  15.             /* 划重点：这里判断是否到达终点 */
  16.             if (cur is target)
  17.                 return step;
  18.             /* 将 cur 的相邻节点加入队列 */
  19.             for (Node x : cur.adj())
  20.                 if (x not in visited) {
  21.                     q.offer(x);
  22.                     visited.add(x);
  23.                 }
  24.         }
  25.         /* 划重点：更新步数在这里 */
  26.         step++;
  27.     }
  28. }

队列 q 就不说了，BFS 的核心数据结构；cur.adj() 泛指 cur 相邻的节点，比如说二维数组中，cur 上下左右四面的位置就是相邻节点；visited 的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要 visited。

二叉树的最小高度

Leetcode-简单
image.png
套用上面的框架，start 起点就是根节点root ，重点 target 就是最靠近根节点的叶子节点，也就是叶子节点的两个子节点都为null。
表达式为：

  1.     if (no.left == null && no.right == null) {
  2.                     return dep;
  3.     }

代码：

  1. public class BFSdemo {
  2.     static int bfs(TreeNode root) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  6.         //队列，存储当前层级所有节点
  7.         Queue<TreeNode> queue = new LinkedList<>();
  8.         queue.add(root);
  9.         int dep = 1;
  11.         while (!queue.isEmpty()) {
  12.             //当前队列大小必须独立常量出来，否则queue.size()的数值不断变化，for循环出错。
  13.             int size = queue.size();
  14.             for (int i = 0; i < size; i++) {
  15.                 //获得队列第一个值并移除
  16.                 TreeNode cur = queue.poll();
  17.                 //结束条件
  18.                 if (cur.left == null && cur.right == null) {
  19.                     return dep;
  20.                 }
  21.                 //将cur节点的子节点加入队列
  22.                 if (cur.left != null) {
  23.                     queue.offer(cur.left);
  24.                 }
  25.                 if (cur.right != null) {
  26.                     queue.offer(cur.right);
  27.                 }
  28.             }
  29.             dep++;
  30.         }
  31.         return dep;
  32.     }
  34.     //[3,9,20,null,null,15,7]
  35.     public static void main(String[] args) {
  36.         TreeNode root = new TreeNode(3);
  37.         root.left = new TreeNode(9);
  38.         root.right = new TreeNode(20);
  40.         root.right.left = new TreeNode(15);
  41.         root.right.right = new TreeNode(7);
  43.         int dep = bfs(root);
  44.         System.out.println(dep);
  45.     }
  46. }
  48. public class TreeNode {
  50.     public int val;
  51.     public TreeNode left;
  52.     public TreeNode right;
  54.     public TreeNode() {}
  56.     public TreeNode(int val) { this.val = val; }
  58.     public TreeNode(int val, TreeNode left, TreeNode right) {
  59.         this.val = val;
  60.         this.left = left;
  61.         this.right = right;
  62.     }
  63. }