前言
深度优先遍历(Depth First Search, 简称 DFS) 与广度优先遍历(Breath First Search)是图论中两种非常重要的算法，常常可以用于树、图的遍历，生产上一般可以用于拓扑排序，寻路(走迷宫)，搜索引擎，爬虫等，他们也是算法面试中的高频考点。
深度优先遍历（DFS）
主要思路是从图中一个未访问的顶点 V 开始，或者是从树的根节点开始，沿着一条路一直走到底（比如说树结构，会沿着树最左侧节点走到头），然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底...，不断递归重复此过程，直到所有的顶点都遍历完成，它的特点是不撞南墙不回头，先走完一条路，再换一条路继续走。
深度优先遍历一般有两这种方式：递归，栈
如同所示，深度优先遍历的遍历顺序是12，5，1，6，19，13
这也是经典的前序遍历，同理中序遍历，后序遍历都可以通过深度优先的思想进行遍历
下边是通过递归的方式进行深度优先遍历
/**
* 二叉树
**/
public class BinaryTree {
// 根节点
private TreeNode root;
/*
-------------------遍历二叉树
1
2 3
4 5 6 7
递归的思想：
前序遍历 ： 1, 2,4,5, 3,6,7
中序遍历 ： 4,2,5, 1, 6,3,7
后序遍历 ： 4,5,2, 6,7,3, 1
*/
public void frontShow() {
System.out.println("前序遍历：");
if (root!=null) {
root.frontShow();
} else {
System.out.println("空的树");
}
System.out.println();
}
public void midShow() {
System.out.println("中序遍历：");
if (root!=null) {
root.midShow();
} else {
System.out.println("空的树");
}
System.out.println();
}
public void rearShow() {
System.out.println("后序遍历：");
if (root!=null) {
root.rearShow();
} else {
System.out.println("空的树");
}
System.out.println();
}
}/**
* 二叉树节点
**/
@Data
public class TreeNode {
// 节点的权
private int value;
private Byte data;
// 左子节点
TreeNode leftNode;
// 右子节点
TreeNode rightNode;
/*
-------------------遍历二叉树
1
2 3
4 5 6 7
递归的思想：
前序遍历 ： 1, 2,4,5, 3,6,7
中序遍历 ： 4,2,5, 1, 6,3,7
后序遍历 ： 4,5,2, 6,7,3, 1
*/
public void frontShow() {
// 遍历当前节点
System.out.print(value + "\t");
// 左节点
if(leftNode!=null) {
leftNode.frontShow();
}
// 右节点
if(rightNode!=null) {
rightNode.frontShow();
}
}
public void midShow() {
// 左节点
if(leftNode!=null) {
leftNode.midShow();
}
// 遍历当前节点
System.out.print(value + "\t");
// 右节点
if(rightNode!=null) {
rightNode.midShow();
}
}
public void rearShow() {
// 左节点
if(leftNode!=null) {
leftNode.rearShow();
}
// 右节点
if(rightNode!=null) {
rightNode.rearShow();
}
// 遍历当前节点
System.out.print(value + "\t");
}
}通过栈的方式进行遍历
/**
* 通过栈来实现 dfs
* @param root
*/
public void dfsWithStack(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
// 先把根节点压栈
stack.push(root);
while (!stack.isEmpty()) {
TreeNode treeNode = stack.pop();
// 遍历当前节点
System.out.print(treeNode.value + "\t");
// 先压右节点
if (treeNode.right != null) {
stack.push(treeNode.right);
}
// 再压左节点
if (treeNode.left != null) {
stack.push(treeNode.left);
}
}
} 广度优先遍历（BFS）
广度优先遍历，指的是从图的一个未遍历的节点 V 开始，或者是从树的根节点开始，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。从树的角度看就是从根节点开始一层一层的遍历。
广度优先遍历的方式一般都是借助队列
/**
* 使用队列实现 bfs
* @param root
*/
private static void bfsWithQueue(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.println("value = " + node.value);
TreeNode left = node.left;
if (left != null) {
queue.add(left);
}
TreeNode right = node.right;
if (right != null) {
queue.add(right);
}
}
} 实例
DFS 实例
给定一组部门数据（包含部门id，父级部门id，部门名称），需要按上下级部门分层次打印出来，这个时候我们就可以利用深度优先遍历的思想，首先找到一级部门，也就是树的根节点，然后一直去查它的子部门，直到将一个部门的所有子部门（包含子部门的子部门...）遍历完，就可以得到我们的部门树。
package com.zhj.interview;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* @author zhj
*/
public class Test05 {
static class Node {
int id;
int parentId;
String name;
public Node(int id, int parentId, String name) {
this.id = id;
this.parentId = parentId;
this.name = name;
}
}
public static void main(String[] args) {
List<Node> nodeList = Arrays.asList(
new Node(1, 0, "AA"),
new Node(2, 1, "BB"),
new Node(3, 1, "CC"),
new Node(4, 3, "DD"),
new Node(5, 3, "EE"),
new Node(6, 2, "FF"),
new Node(7, 2, "GG"),
new Node(8, 4, "HH"),
new Node(9, 5, "II"),
new Node(10, 0, "JJ"),
new Node(11, 10, "KK"),
new Node(12, 10, "LL"),
new Node(13, 12, "MM"),
new Node(14, 13, "NN"),
new Node(15, 14, "OO")
);
print(nodeList);
}
public static void print(List<Node> nodeList) {
//todo
List<Node> rootList = findRoot(nodeList);
for (Node node : rootList) {
System.out.println(node.name);
getSon(nodeList, node.id, 1);
}
}
/**
* 查找根节点
* @param nodeList
* @return
*/
public static List<Node> findRoot(List<Node> nodeList) {
List<Node> rootList = new ArrayList<>();
for (Node node : nodeList) {
boolean isNotRoot = false;
for (Node n : nodeList) {
if (node.parentId == n.id) {
isNotRoot = true;
break;
}
}
if (!isNotRoot) {
rootList.add(node);
}
}
return rootList;
}
/**
* 查找并打印孩子节点
* @param nodeList
* @param id
* @param level
* @return
*/
public static Node getSon(List<Node> nodeList,Integer id, int level) {
for (Node node : nodeList) {
if (node.parentId == id) {
for (int i = 0; i < level; i++) {
System.out.print("\t");
}
System.out.println(node.name);
getSon(nodeList, node.id, level+1);
}
}
return null;
}
}打印结果：
AA
BB
FF
GG
CC
DD
HH
EE
II
JJ
KK
LL
MM
NN
OOBFS 实例
力扣107 二叉树的层序遍历，般能用DFS的也可以使用BFS解决，但是他们各自特点不一样，BFS是按层遍历，DFS是一条路走到头，走投无路才会返回走另一条路，我们应该充分发挥算法的优势。
package com.zhj.leetcode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/**
* 力扣107 二叉树层遍历
*/
public class Test107 {
public static void main(String[] args) {
TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);
root.right.right = new TreeNode(18);
List<List<Integer>> res = bfs(root);
for (List<Integer> re : res) {
for (Integer i : re) {
System.out.print(i + "\t");
}
System.out.println();
}
}
public static List<List<Integer>> bfs(TreeNode root) {
LinkedList<List<Integer>> result = new LinkedList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> subset = new ArrayList<>();
while (size > 0) {
TreeNode cur = queue.poll();
subset.add(cur.val);
if (cur.left != null) {
queue.add(cur.left);
}
if (cur.right != null) {
queue.add(cur.right);
}
size--;
}
result.addFirst(new ArrayList<>(subset));
}
return result;
}
}
