最近在学习算法与数据结构，在了解了费曼学习法后，我决定写一个专栏来专门讲述这方面的知识。一方面可以以讲带学最有效率的掌握知识，二来可以将知识分享给大家，除此之外在未来还可以查看他们来复习知识，真是个一举三得的事情，话不多说，我们就开始吧，今天首先从”深度优先搜索“（DFS）算法开始。

I. 算法定义

DFS是一种用于遍历、搜索树或图的一种搜索算法。搜索的灵感顾名思义：先递归下去，再回溯上来。意思是说，当人们需要在图、搜索树或者遍历中搜索某个Object时，DFS会首先一路走到底，直到不能再下，如果找到了对象，就return回去，没有找到就回溯到上一步的地方，然后换一条路继续一路走到黑重复以上过程直到找到对象或者找遍所有Object为止。

右下图是DFS在查找树上应用的例子。假如我们要找的值为节点2，DFS会首先按一个路线走到不能再走，也就是0->1->3。因为节点3没有子节点了，DFS会回到上一级，也就是节点1的位置，然后按照另一条路走到黑。也就是0->1->3->4。由于4没有子节点，DFS会回到节点1，然后节点1所有的子节点都已经去过了，于是乎再回到节点0，然后去到节点2，最终找到它，路线就是0->1->3->4->2。

DFS是一种非常古老的算法，早在古希腊神话中，雅典城的英雄忒休斯正是靠着阿里阿德涅之线在米诺斯王宫找到了米诺陶诺斯之牛并杀掉它为民除害的。

II. 实现方法

通常DFS用递归(Recursion)来实现。步骤如下：

1. 首先设置递归的边界，当遇到边界（走到底时）停止递归。
2. 设置递归的过程。

III. 经典习题

1. Same Tree (Leetcode 100)

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

这道题非常的简单，判断两个binary tree是否相同。按照DFS算法的思路，我们步骤如下：

1. 设置递归的边界，也就是当两棵树的中的一棵的节点没有子节点时，停止递归。

2. 如果两棵树中某个相同位置节点的值不一样，return false。

3. 如果两棵树中某个相同位置节点的值一样，那么执行递归, 判断此节点的左右两个子节点是否相等直到没有子节点为止。

   代码

   /**
    * 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;
    *     }
    * }
    */
   class Solution {
       public boolean isSameTree(TreeNode p, TreeNode q) {
           if (p == null || q == null){
               return p == null && q == null;
           }else if (p.val == q.val){
               return (isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
           }else{
               return false;
           }
       }
}

1. Permutations(Leetcode 46)

Given a collection of distinct integers, return all possible permutations.

这道题要我们写一个程序：输入一个没有重复数字的数组，返回此数组中所有项的所有排列组合方式。

这道题我们依然可以用DFS来解决。我们可以拿输入[1,2,3]来举例，其思路如下：

首先我们需要以下变量：

1. int [ ] nums，input数组。
2. Linkedlist result，用于储存结果并返回。
3. HashSet set，用来记录目前已经使用过的数字，避免重复（如[1,1,1]）。
4. Linkedlist currentList，用来储存提取的数字，当完成提取时将结果push到result中。

实现步骤如下：

1. 通过观察这个表格我们很容易就找到了这个递归的边界：那就是当提取的数组的length与input数组length相等时，将currentlist中的值添加到result并停止递归，开始向上回溯。

2. 接着，递归的思路如下：

   a. 首先使用for循环来遍历nums中的所有数字。

   b. 如果这个遍历到的数字之前没有使用过，就将其添加到current list里，并且添加到set里标记为已使用。

   c. 将新的result, currentlist 以及set传入到下一层函数中进行递归。

   d. 当递归回溯上来后将添加到set和currentlist中的数字删除，让他们回到原型。

代码如下：

   class Solution {
       public List<List<Integer>> permute(int[] nums) {
           List<List<Integer>> result = new LinkedList<>();
           if (nums == null || nums.length == 0) return result;
           Arrays.sort(nums);
           dfs(nums, result, new LinkedList<Integer>(), new HashSet<Integer>());
           return result;
       }
   
       private void dfs(int[] nums, List<List<Integer>> result, List<Integer> curr, HashSet<Integer> set) {
           if (set.size() == nums.length){
               result.add(new LinkedList<Integer>(curr));
           }else{
               for (int i=0; i<nums.length;i++){
                   if (!set.contains(nums[i])){
                       curr.add(nums[i]);
                       set.add(nums[i]);
                       dfs(nums, result, curr, set);
                       set.remove(nums[i]);
                       curr.remove(curr.size()-1);
                   }
               }
           }
       }
   }

IV. 总结

DFS是一种在图、搜索树和遍历中非常经典且常用的算法。其思路为用递归的方式首先延一条路线搜索到底，如果到底了还没搜索到对象，就回溯到上一层并按另一条路线再走到底，如此重复直到找到对象或者遍历完整个集合为止。