深度优先搜索和广度优先搜索

一、DFS和BFS

深度优先搜索（DFS）：

广度优先搜索（BFS）：

二、相关题目

1、LeetCode102：二叉树的层次遍历

给定一个二叉树，返回其按层次遍历的节点值（即逐层地，从左到右访问所有节点）

例如：

给定二叉树：[3,9,20,null,null,15,7]

3 / \ 9 20 / \ 15 7

返回其层次遍历结果：

[ [3], [9,20], [15,7] ]

1）DFS，递归

List<List<Integer>> result = new ArrayList<>(); public List<List<Integer>> levelOrder(TreeNode root) { helper(root, 0); return result; } private void helper(TreeNode root, int depth) { if (root == null) return; if (result.size() <= depth) result.add(new ArrayList<>()); result.get(depth).add(root.val); helper(root.left, depth + 1); helper(root.right, depth + 1); }

2）BFS，使用队列实现

public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { List<Integer> tmp = new ArrayList<>(); int length = queue.size(); for (int i = 0; i < length; ++i) { TreeNode node = queue.remove(); tmp.add(node.val); if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } result.add(tmp); } return result; }

2、LeetCode515：在每个树行中找最大值

您需要在二叉树的每一行中找到最大的值

示例：

输入： 1 / \ 3 2 / \ \ 5 3 9 输出：[1, 3, 9]

题解：

public List<Integer> largestValues(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int max = queue.getFirst().val; int length = queue.size(); for (int i = 0; i < length; ++i) { TreeNode node = queue.remove(); if (max < node.val) max = node.val; if (node.left != null) queue.add(node.left); if (node.right != null) queue.add(node.right); } result.add(max); } return result; }

3、LeetCode200：岛屿数量

给定一个由’1’（陆地）和’0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围

示例 1：

输入: 11110 11010 11000 00000 输出: 1

示例 2：

输入: 11000 11000 00100 00011 输出: 3

题解：

public int numIslands(char[][] grid) { if(grid.length==0||grid[0].length==0) return 0; int num=0; for(int i=0;i<grid.length;++i){ for(int j=0;j<grid[0].length;++j){ if(grid[i][j]=='1'){ num++; dfs(grid,i,j); } } } return num; } private void dfs(char[][] grid,int i,int j){ int ni=grid.length; int nj=grid[0].length; if(i<0||j<0||i>=ni||j>=nj||grid[i][j]=='0') return; grid[i][j]='0'; dfs(grid,i+1,j); dfs(grid,i-1,j); dfs(grid,i,j+1); dfs(grid,i,j-1); }

解析：

线性扫描整个二维网格，如果一个结点包含1，则以其为根结点启动深度优先搜索。在深度优先搜索过程中，每个访问过的结点被标记为0。计数启动深度优先搜索的根结点的数量，即为岛屿的数量

常用数据结构的时间、空间复杂度：

https://www.bigocheatsheet.com/