深度优先算法 深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。
过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
深度优先的基本原则：按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到满足条件的目标为止。
常用的算法模板
//深度优先搜索dfs class Solution { public void dfs(char[][] source,int x,int y){//遍历的对象一般为树节点，图节点，二维数组等，这里以二维数组为例 if (终止条件 || 目标节点已访问) {return;}//符合终止条件或已访问过该节点，退出 source[x][y] = '0';//对已访问的节点进行标记，可以直接在原节点上修改，也可以使用一个visited数组进行标记 ......//此处为对目标节点的操作，如赋值，读取数等 dfs(source,x+1,y);//递归搜索下一次遍历节点 dfs(source,x-1,y); ...... } public int result(char[][] source){//若需要返回结果，在一个新的类中实现 int res = 0; ......//初始化 for (int i = 0;i < source.length;i++){ for (int j = 0;j < source[0].length;j++){ if (符合dfs开始节点条件) { res++;//对需要返回的结果进行赋值，累加等操作 dfs(source,i,j);//开始dfs } } } return res; } }二叉树的最大深度
class Solution { int i =0; public int maxDepth(TreeNode root) { dfs(root,0); return i; } public void dfs(TreeNode root,int d) { if(root==null) //终结条件 return; d++; //深度加一 i = Math.max(i,d); dfs(root.left,d);//深度遍历 dfs(root.right,d); } }对称二叉树 给定一个二叉树，检查它是否是镜像对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3
注意之前写这个题老是陷入一个误区 就是 比较root节点的左右问题 就造成 问题的无解
这样的代码主要是对 对称树的条件提取的错误
public boolean isSymmetric(TreeNode root) { if(root ==null) return true; else if(root.left==null&&root.right==null) return true; else return isSymmetric(root.left) && isSymmetric(root.right); }正确的 镜像树实际上应该是
若 root == null, 直接返回 true；否则，判断 root.left 与 root.right 这两棵子树是否对称： + 判断 root.left 与 root.right 这两个节点的值是否相等 + 判断 root.left 的左子树与 root.right 的右子树是否对称 + 判断 root.left 的右子树与 root.right 的左子树是否对称 class Solution { public boolean isSymmetric(TreeNode root) { if(root ==null) return true; return dfs(root.left,root.right); } public boolean dfs(TreeNode left,TreeNode right) { if(left==null&&right==null) return true; if((left!=null&&right!=null)&&(left.val ==right.val)) return dfs(left.left,right.right)&&dfs(left.right,right.left); else return false; } }岛屿数量 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。
class Solution { int nums =0; public int numIslands(char[][] grid) { if(grid.length==0) return 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if(grid[i][j]=='1') nums++;//计算岛的数量 dfs(grid,i,j);深度递归 } } return nums; } public void dfs(char c[][],int i,int j){ if(i>=c.length||j>=c[0].length||i<0||j<0)//非法边界值 { return; } if(c[i][j]=='0') //不是岛 return; else{//是岛 开始递归 c[i][j]='0';//遍历过的标0 dfs(c,i+1,j); dfs(c,i,j+1); dfs(c,i-1,j); dfs(c,i,j-1); } } }查并集也可以解决 这个为题 这个算法很有意思 查并集的江湖纷争
验证搜索二叉树
** 实际上每次遍历完 我们总是可以把当前节点的子树的最大值提取出来 然后到达根 在和它比 到达右子树时候 恰好 根中的最大值也已经赋给了MIN **
实际上该题就是中序遍历然后 用一个MIN变量时刻保存着 树中的最小值
搜索二叉树的中序遍历就是一个递增的序列
class Solution { //注意这个min必须是全局变量才可 因为我们每次递归调用函数的时候都要对这个值 做更改 // 所以不能定义到方法体中去 //这个long min 是为了防止根节点 最小值 这样的话我们在比较根节点的时候就直接返回false了 //所以要定义一个比INT_MIN更小的数字才可以 long min = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { //运用中序遍历才可 return mid(root); } public boolean mid(TreeNode root){ //跳出条件 if(root==null) return true; //左节点 必须使用if 来进行判断 不然就直接返回结果了 if(!mid(root.left)) return false; //访问本节点 if(root.val<=min) return false; min = (long)root.val; //访问右节点 return mid(root.right); } }二叉树的右视图
这题最容易想到的做法肯定的广度遍历了
但是感觉深度遍历做这种题目好有意思
class Solution { List<Integer> res = new ArrayList<>(); public List<Integer> rightSideView(TreeNode root) { dfs(root, 0); // 从根节点开始访问，根节点深度是0 return res; } private void dfs(TreeNode root, int depth) { if (root == null) { return; } // 先访问 当前节点，再递归地访问 右子树 和 左子树。 //这个判断真的是神了 .......... if (depth == res.size()) { // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。 res.add(root.val); } depth++; dfs(root.right, depth); dfs(root.left, depth); } }作者：sweetiee 链接：链接
岛的最大
几乎和岛屿数量是同样的模板 就是多加了 一个当前岛屿的面积的tmp变量 和nums表示的是最大岛屿
class Solution { int nums =0; int tmp=0; public int maxAreaOfIsland(int[][] grid) { if(grid.length==0) return 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if(grid[i][j]==1){ tmp=0; dfs(grid,i,j); } } } return nums; } public void dfs(int c[][],int i,int j){ if(i>=c.length||j>=c[0].length||i<0||j<0)//非法边界值 { return; } if(c[i][j]==0) //不是岛 return; else{//是岛 开始递归 tmp++; nums =Math.max(tmp,nums); c[i][j]=0;//遍历过的标0 dfs(c,i+1,j); dfs(c,i,j+1); dfs(c,i-1,j); dfs(c,i,j-1); } } }子集
class Solution { List<List<Integer>> res = new ArrayList<>();//保存结果 LinkedList<Integer> tmp = new LinkedList<>();//临时值 public List<List<Integer>> subsets(int[] nums) { int i=0; dfs(nums,i,tmp,res); return res; } public void dfs(int[] nums, int i, LinkedList<Integer> tmp, List<List<Integer>> res) { res.add(new LinkedList<>(tmp));//加入没有条件 因为在之前已经剪过枝了 for (int j = i; j < nums.length; j++) { if(baohan(tmp,nums[j])) //tmp中的数字不能重复 continue; tmp.addLast(nums[j]); if(baohan2(res,tmp)) //res和tmp也不能重复 { tmp.removeLast(); continue; } dfs(nums, i + 1, tmp, res); tmp.removeLast(); } } public boolean baohan(List tmp,int i){ //同一份数组中不能又重复 if(tmp.contains(i)) return true; return false; } public boolean baohan2(List<List<Integer>> tmp,List<Integer> s) //结果数组和新要添加的数组不能重复 { for (List<Integer> uu: tmp){ if(uu.containsAll(s)&&s.containsAll(uu))//注意 这个方法可以判断两个数组完全相等 return true; } return false; } }被围绕的区域 题目中解释说被包围的区间不会存在于边界上，所以我们会想到边界上的 O 要特殊处理，只要把边界上的 O 特殊处理了，那么剩下的 O替换成 X 就可以了。 问题转化为，如何寻找和边界联通的 O
class Solution { public void solve(char[][] board) { for (int i = 0; i <board.length; i++) { for (int j = 0; j < board[0].length; j++) { if(i==0||j==0||i==board.length-1||j==board[0].length-1) { if(board[i][j]=='O'){ // board[i][j] = '#'; dfs(board,i,j); //转化和边界0相邻的字节 都变成#好 //那么没有被变成#号的X就是被包围的区域了 } } } } System.out.println(Arrays.deepToString(board)); for (int i = 0; i <board.length; i++) { for (int j = 0; j < board[0].length; j++) { if(board[i][j]=='#') board[i][j] = 'O';//改变这个没有包围的 else if(board[i][j] =='O') board[i][j] ='X';// } } } public void dfs(char[][] board,int i,int j){ if(i < 0 || j < 0 ||i >= board.length || j >= board[0].length || board[i][j] == 'X' || board[i][j] == '#') //board[i][j] == '#' 避免重复查询的问题 return; if(board[i][j]=='O'){ board [i][j]='#'; dfs(board,i+1,j);//右 dfs(board,i,j+1);//上 dfs(board,i-1,j);//左 dfs(board,i,j-1);//下 } } }