深度优先搜索DFS

一条道路走到底，直到走不下去为止。然后再返回上一节点，继续重复刚才的过程

代码模板

DFS：

使用栈来保存已经走过的节点，
节点按照深度优先的次序被访问并依次压入栈中，并已相反的次序出栈进行新的检测。

DFS（dep，……）//dep代表目前DFS的深度
{
    if（找到解||走不下去了）
    {
        ……；
        return；
    }
    else
    {
        // 模拟下一种情况；
        DFS（dep+1，……）；
    }
}

实例

leetcode797题

题目如下：

给你一个有 n 个节点的有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。
译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。
输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

需要两个变量，ans用来存储所有的路径，stack作为栈来记录路径上已经走过的点，使用队列来实现。

List<List<Integer>> ans = new ArrayList<List<Integer>>();

// 使用栈来记录路径上的点
Deque<Integer> stack = new ArrayDeque<Integer>();

写一个函数dfs用于深搜：
这里graph代表输入的图，x代表当前遍历到了几号节点，n代表最后一个节点的编号（因为所有的路径的终点都是最后一个节点）

public void dfs(int[][] graph, int x, int n) {
    // 如果遍历到了最后一个节点，就将其添加到结果数组中
    if (x == n) {
        ans.add(new ArrayList<>(stack));
        return;
    }
    //节点按照深度优先的次序被访问并依次压入栈中，并以相反的次序出栈进行新的检测。
    for (int y : graph[x]) {
      // 将节点压入栈中
        stack.offerLast(y);
      // 求从节点y到最后一个节点的所有路径
        dfs(graph,y,n);
      // 将y节点出栈
        stack.pollLast();
    }
}

在主函数中进行调用，这里首先要将0号节点入栈，因为所有的路径都要从0号节点开始

public  List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    // 从0号节点开始走
    stack.offerLast(0);
    // graph.length-1代表最后一个节点的编号
    dfs(graph,0,graph.length-1);
    return ans;
}

leetcode112题：路径总和

题目如下：

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点是指没有子节点的节点。
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
/** * Definition for a binary tree node.
*public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
*/

首先定义两个变量，ans用来存储所有的路径，stack作为栈来记录路径上已经走过的点，使用队列来实现。

List<List<TreeNode>> ans = new ArrayList<List<TreeNode>>();

// 使用栈来记录路径上的点
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();

写一个函数dfs用于深搜：

public void dfs(TreeNode node) {
    if(node == null){
        return;
    }
   	// 如果已经得到叶子结点
    if(node.left==null && node.right==null){
        ans.add(new ArrayList<>(stack));
        return;
    }
    else{
    // 遍历左子树
     if(node.left!=null){
        stack.offerLast(node.left);
        dfs(node.left);
        stack.pollLast();
      }
    // 遍历右子树
     if(node.right!=null){
       	 stack.offerLast(node.right);
         dfs(node.right);
         stack.pollLast();
     }
		}
}

在主函数中进行调用，这里首先要将根节点入栈，因为所有的路径都要从根节点开始

public boolean hasPathSum(TreeNode root, int targetSum) {
  // 将根节点入栈
  if(root!=null) stack.offerLast(root);
  // 进行深搜并将结果存入ans中
  dfs(root);
  for(int i=0;i<ans.size();i++){
    int sum=0;
    for(int j=0;j<ans.get(i).size();j++){
      sum+=ans.get(i).get(j).val;
    }
    if(sum==targetSum) return true;
  }
  return false;
}