搜索系列之DFS
算法介绍
DFS（Depth-First-Search），即深度优先搜索 。是一种用于遍历或搜索树或图的算法，这个算法会尽可能深的搜索树的分支。即在搜索到一个新节点时，立即对该节点进行遍历，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。重复此过程直到从源节点出发的所有节点均被访问。
DFS 是图论中经典的算法，因为发现此算法，John Edward Hopcroft 和 Robert Endre Tarjan 于 1986年共同获得了图灵奖。
实现方式
基于栈
因为在搜索到一个新的节点时，需要立即对该新节点进行遍历，因此遍历需要用先进后出的栈来实现。
说白了，就两点：
一条道走到黑：先选择当前节点的一个子节点进行深入，然后对子节点再进行深度优先搜索。
撞到南墙再回头：一直搜索到叶节点，然后向上回溯，再对另一个子节点进行深度优先搜索。
例如遍历以下这棵树
假设我们先遍历左孩子，再遍历右孩子。
我们首先定义出树节点Node：
classTreeNode{
intval;
TreeNodelChild;
TreeNoderChild;
TreeNode(intvalue){
val=value;
}
}
我们创建一个栈用来存放Node节点：
Stack<Node>stack=newStack<Node>;
- 我们首先将根节点root放入到栈中：
- 然后我们出栈栈顶元素并访问之，再判断其是否存在右左孩子，若存在则将其压入栈中。
（注：我们先压入右孩子，再压入左孩子，这样出栈的时候就保证了先遍历到左孩子再是右孩子）
- 紧接着我们又出栈栈顶元素，重复循环步骤 2。
基于栈完整代码：
classSolution{
publicvoiddfs(TreeNoderoot){
if(root==null) returnnull;
Stack<TreeNode>stack=newStack();
stack.push(root);
while(!stack.isEmpty()){
TreeNodecurrNode=stack.pop();
System.out.println(currNode.val);
if(currNode.rChild!=null){
stack.push(currNode.rChild);
}
if(currNode.lChild!=null){
stack.push(currNode.lChild);
}
}
}
}
递归
我们知道函数的调用就是栈结构，所以也可以通过递归实现。
同样上边的例子，其实就是树的前序遍历：
classSolution{
publicvoiddfs(BTreeroot){
if(root==null) returnnull;
System.out.println(root.val);
dfs(root.lChild);
dfs(root.rChild);
}
}
