一、原理

深度优先搜索再得到一个新节点时立即对新节点进行遍历，从节点 0 出发开始遍历，得到到新节点 6 时，立马对新节点 6 进行遍历，得到新节点 4；如此反复以这种方式遍历新节点，直到没有新节点了，此时返回。返回到根节点 0 的情况是，继续对根节点 0 进行遍历，得到新节点 2，然后继续以上步骤。

从一个节点出发，使用DFS对一个图进行遍历时，能够遍历到的节点都是从初始节点可达的，DFS常用来解决这种 可达性 问题。

实现：递归栈（保存当前节点信息，当遍历新节点返回时能继续遍历当前节点）、标记（对已经遍历过的节点进行标记）。

二、应用

数组：

思路：对于没有被访问过且为‘1’的单元格，进行深度优先搜索，搜索过程中更新访问状态数组

class Solution {
    int[][] dir=new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
    boolean[][] visited;
    int m,n;
    public int numIslands(char[][] grid) {
        m=grid.length;
        n=grid[0].length;
        visited=new boolean[m][n];
        for(int i=0;i<m;i++){
            Arrays.fill(visited[i],false);
        }
        int res=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!visited[i][j]&&grid[i][j]=='1'){
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }
    public void dfs(char[][] grid,int x,int y){
        visited[x][y]=true;
        for(int[] arr:dir){
            int newX=x+arr[0];
            int newY=y+arr[1];
            if(newX<0||newX>=m||newY<0||newY>=n||visited[newX][newY]||grid[newX][newY]=='0'){
                continue;
            }
            dfs(grid,newX,newY);
        }
    }
}

树：

思路： dfs过程中改变targetSum的值，直到叶子节点且targetSum为0时找到一条路径。

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>>res=new LinkedList<List<Integer>>();
        Deque<Integer>path=new LinkedList<Integer>();
        dfs(root,targetSum,path,res);
        return res;
    }
    public void dfs(TreeNode root,int targetSum,Deque<Integer>path,List<List<Integer>>res){
        if(root==null){
            return;
        }
        path.offerLast(root.val);
        targetSum-=root.val;
        if(targetSum==0&&(root.left==null&&root.right==null)){
            res.add(new LinkedList<Integer>(path));
        }
        dfs(root.left,targetSum,path,res);
        dfs(root.right,targetSum,path,res);
        path.pollLast();
    }
}

思路：第一次深度优先从root开始搜索每个节点的父节点并保存在哈希表中，因为每个节点的值不充分，可以用节点的值作为key，第二次深度搜索从目标节点开始，对节点的左子树、右子树、根分别进行搜索，找到与目标节点距离为K的节点记录到结果。

class Solution {
    Map<Integer,TreeNode>parents=new HashMap<>();
    List<Integer>res=new ArrayList<>();
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        findParents(root);
        findans(target,null,k,0);
        return res;
    }
    public void findParents(TreeNode root){
        if(root==null) return;
        if(root.left!=null){
            parents.put(root.left.val,root);
            findParents(root.left);
        }
        if(root.right!=null){
            parents.put(root.right.val,root);
            findParents(root.right);
        }
    }
    public void findans(TreeNode node,TreeNode from,int k,int depth){
        if(node==null){
            return;
        }
        if(depth==k){
            res.add(node.val);
            return;
        }
        if(node.left!=from){
            findans(node.left,node,k,depth+1);
        }
        if(node.right!=from){
            findans(node.right,node,k,depth+1);
        }
        if(parents.get(node.val)!=from){
            findans(parents.get(node.val),node,k,depth+1);
        }
    }
}

图：

思路：邻接表构图，DFS搜索过程中判断是否有环

class Solution {
    List<List<Integer>>graph;
    int[] visited;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        graph=new ArrayList<>();
        visited=new int[numCourses];
        Arrays.fill(visited,0);
        for(int i=0;i<numCourses;i++){
            graph.add(new ArrayList<>());
        }
        int n=prerequisites.length;
        for(int i=0;i<n;i++){
            graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
        }
        for(int i=0;i<numCourses;i++){
            if(!dfs(i)){
                return false;
            }
        }
        return true;
    }
    public boolean dfs(int i){
        if(visited[i]==1) return false;
        if(visited[i]==-1) return true;
        visited[i]=1;
        for(int j:graph.get(i)){
            if(!dfs(j)){
                return false;
            }
        }
        visited[i]=-1;
        return true;
    }
}