【LeetCode14种套路】二、深度优先搜索_leetcode 深度优先搜索

前言

大家好，我是春风。

今天继续学习leetcode套路二：深度优先搜索

适用数据结构

• 树（二叉树）
• 网格
• 图（有向图、无向图）

问题特点

• 已知树或者图的存储数据结构，搜索或者遍历元素；
• 求解有多少种情况等，未给定数据结构，但需要通过树或者图的结构+遍历来求解

算法特点

使用深度优先搜索（DFS）对一个图或者树进行遍历时，每次得到一个新节点时，立即对新节点进行遍历，然后递归回到当前节点。所以一次遍历到的节点都是初始节点可达的，DFS也常用来求解这种可达性问题。

使用算法时一般需要考虑两个问题：

1.栈：用栈来保存当前节点信息，当遍历完新节点返回时能够继续遍历当前节点，可以使用递归栈。
（每次遍历一个节点，先入栈，当栈顶元素没有子节点时，栈顶元素出栈，最后栈中所有元素都出栈后，即遍历完成）
2.标记：和BFS一样同样需要对已经遍历过的节点进行标记
（图结构有首尾相连的情况，需要在栈的基础上加标记判断）

例题

1. 给定一个数组，求它的全排列

输入: [1,2,3] 
输出: [123][132][213][231][312][321]
解释: 利用线性数据结构进行深度优先遍历
重点：递归+记录当前元素添加状态

  场景二：给定数组包含重复字符，使用hash[]++记录元素添加次数，为0时，则不添加

static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res= new ArrayList<>();