【40讲系列8】广度优先搜索、深度优先搜索
一、理论
BFS用到队列,只有非递归写法。
应用到树时,不需要标记该节点是否走过。而应用到图结构时,需要标记某个节点是否已被访问过。
DFS需要用栈,有递归和非递归写法,推荐使用递归写法。
二、典型例题
①:二叉树层次遍历(LC102、剑指22.从上往下打印二叉树)
方法1:树的BFS,需要用队列。 (方法1见剑指22)
方法2:还可以用DFS,为了让递归的过程中同一层的节点放到同一个列表中,在递归时要记录每个节点的深度 level。递归到新节点要把该节点放入 level 对应列表的末尾(当遍历到一个新的深度 level,而最终结果 res 中还没有创建 level 对应的列表时,要在res新建一个)。
方法2(DFS):
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root != null){ dfs(res,root,0); } return res; } private void dfs(List<List<Integer>> res, TreeNode root, int level){ if (root == null) return; if (res.size() - 1 < level){ res.add(new ArrayList<>()); } res.get(level).add(root.val); dfs(res,root.left,level+1); dfs(res,root.right,level+1); } }
②:二叉树最大深度(LC104、剑指38.二叉树的深度)
方法1:递归。树的深度=max(左子树深度,右子树深度)+1
方法2:BFS。层序遍历时记录层数即可
方法3:DFS,模仿上一题的写法。
方法1和方法2 见剑指38.二叉树的深度
方法3(DFS):
class Solution { int max = 0; // 全局,记录 public int maxDepth(TreeNode root) { if (root == null) return 0; dfs(root,1); return max; } private void dfs(TreeNode root, int level){ if (root == null) return; /*if (max < level){ // 每次到了新节点都判断一下 max = level; }*/ if (root.left == null && root.right == null){ // 到了叶子节点再判断并更新max max = max < level ? level : max; } dfs(root.left,level + 1); dfs(root.right,level + 1); } }
③:二叉树最小深度(LC111)
方法1:递归。需要单独处理没有左子树或没有右子树的特殊情况
方法2:BFS
方法3:DFS
class Solution { int min = Integer.MAX_VALUE; public int minDepth(TreeNode root) { // 方法1. 递归 if (root == null) return 0; int left = minDepth(root.left); int right = minDepth(root.right); // 如果left和right都为0,说明是叶子节点,返回1即可, // 如果left和right有一个为0,说明其中一个子节点为空,此时返回它另一个子节点的最小深度+1即可。 // 如果left和right都不为0,说明左右孩子都不为空,返回最小深度的+1即可。 return (left == 0 || right == 0) ? 1 + left + right : Math.min(left,right) + 1; // 方法2. BFS /* if (root == null) return 0; int min = 0; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ int levelNums = queue.size(); min++; for (int i = 0; i < levelNums; i++) { TreeNode cur = queue.poll(); if (cur.left == null && cur.right == null) // 最先找到的叶子节点的深度一定最小 return min; if (cur.left != null) queue.offer(cur.left); if (cur.right != null) queue.offer(cur.right); } } return -1; */ // 方法3 :DFS /* if (root == null) return 0; dfs(root, 1); return min; */ } private void dfs(TreeNode root,int level){ if (root == null) return; if (root.left == null && root.right == null){ // 每次到叶子节点时 更新min min = level < min ? level : min; } dfs(root.left,level+1); dfs(root.right,level+1); } }
☆☆☆④:生成所有可能的有效括号组合(LC22)
思路:深搜回溯。每步要么增加一个左括号,要么增加一个右括号,是一二叉的选择,所以可以用深搜。但是并不是每个分支都符合要求,如果右括号使用的比左括号多的话就已经不是正确括号了,没必要继续dfs这个分支了,所以加if来剪枝。
class Solution { List<String> res = new ArrayList<>(); public List<String> generateParenthesis(int n) { if (n == 0) return res; dfs(0,0, n,""); return res; } private void dfs(int left, int right,int n, String str){ if (left == n && right == n){ // 左右括号都用完了 res.add(str); return; } if (left < n){ dfs(left + 1,right,n,str + "("); } // 左括号比右括号多才可以匹配,此时才放右括号。 相当于剪枝 if (right < n && left > right){ dfs(left,right + 1,n,str + ")"); } } }