BFS问题处理模板

  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. }

BFS典型案例

LeetCode 102. 二叉树的层序遍历

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         return bfs(root);
  4.     }
  6.     private List<List<Integer>> bfs(TreeNode root) {
  7.         List<List<Integer>> result = new ArrayList<>();
  8.         if (root == null) {
  9.             return result;
  10.         }
  11.         //BFS类型问题模板, 如果是图等其他结构，还需要用set等保存已经访问过的节点，避免重复访问
  12.         //1.初始化Queue，添加头结点
  13.         Queue<TreeNode> queue = new LinkedList<>();
  14.         queue.offer(root);
  16.         //遍历Queue
  17.         while (!queue.isEmpty()) {
  18.             int size = queue.size();
  19.             List<Integer> row = new ArrayList<>();
  20.             for (int i=0; i< size; i++) {
  21.                 TreeNode node = queue.poll();
  22.                 row.add(node.val);
  23.                 if (node.left != null) {
  24.                     queue.offer(node.left);
  25.                 }
  26.                 if (node.right != null) {
  27.                     queue.offer(node.right);
  28.                 }
  29.             }
  30.             result.add(row);
  31.         }
  32.         //其他处理
  33.         return result;
  34.     }
  35. }

DFS问题处理模板

DFS问题的递归写法：
WechatIMG2.png
DFS的非递归写法
WechatIMG3.png

DFS典型案例

LeetCode 200. 岛屿数量

  1. class Solution {
  2.     public int numIslands(char[][] grid) {
  3.         //处理边界
  4.         if (grid.length == 0) {
  5.             return 0;
  6.         }
  7.         int m = grid.length;
  8.         int n = grid[0].length;
  9.         int count = 0;
  10.         for (int i=0; i<m; i++) {
  11.             for (int j=0; j< n; j++) {
  12.                 if (grid[i][j] == '1') {
  13.                     count++;
  14.                     dfs(i, j, m, n, grid);
  15.                 }
  16.             }
  17.         }
  18.         return count;
  19.     }
  21.     private void dfs(int i, int j, int m, int n, char[][] grid) {
  22.         if (i<0 || i>=m || j<0 || j>=n || grid[i][j] != '1') {
  23.             return;
  24.         }
  25.         grid[i][j] = '0';
  26.         dfs(i-1, j, m, n, grid);
  27.         dfs(i+1, j, m, n, grid);
  28.         dfs(i, j-1, m, n, grid);
  29.         dfs(i, j+1, m, n, grid);
  30.     }
  31. }

LeetCode 113. 路径总和 ||

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
  12.         List<List<Integer>> result = new ArrayList<>();
  13.         if (root == null) {
  14.             return result;
  15.         }
  16.         dfs(root, 0, sum, new ArrayList<>(), result);
  17.         return result;
  18.     }
  20.     private void dfs(TreeNode root, int now,  int sum, List<Integer> path, List<List<Integer>> res) {
  21.         if (root == null) {
  22.             return;
  23.         }
  24.         //这里把root加入进去
  25.         path.add(root.val);
  26.         if (root.left == null && root.right == null) {
  27.             if (sum == root.val+ now) {
  28.                 res.add(path);
  29.             }
  30.             return;
  31.         } 
  32.         if (root.left != null) {
  33.             dfs(root.left, now + root.val, sum, new ArrayList<>(path), res);
  34.         }
  35.         if (root.right != null) {
  36.             dfs(root.right, now + root.val, sum, new ArrayList<>(path), res);
  37.         } 
  38.     }
  39. }