从二叉树遍历深入理解BFS和DFS

1. 介绍

1.1 基础

BFS（Breadth-First Search，广度优先搜索）和 DFS（Depth-First Search，深度优先搜索）是两种常见的图和树的遍历算法。

BFS：从根节点（或起始节点）开始，逐层地对节点进行访问，先访问距离起始节点最近的所有节点，再依次访问距离更远的节点，像水波纹一样一层一层向外扩散。以下图为例：可以理解为BFS是横向遍历。在实现方案上一般使用队列来实现。

DFS：从根节点（或起始节点）开始，沿着一条路径尽可能深地访问节点，直到无法继续，然后回溯到上一个节点，再沿着另一条路径继续深入，直到访问完所有可达节点。以上图为例：可以理解为BFS是纵向遍历。在实现方案上一般使用递归或栈来实现。

1.2 复杂度分析

时间复杂度：对于图来说，BFS 和 DFS 的时间复杂度都是 (O(V + E))，其中 (V) 是顶点数，(E) 是边数。因为在遍历过程中，每个顶点和每条边都需要被访问一次。对于树结构，由于边数 (E = V - 1)，时间复杂度为 (O(V))。

空间复杂度：BFS 的空间复杂度主要取决于队列的最大元素数量，最坏情况下为 (O(V))。DFS 的空间复杂度主要由递归调用栈的深度决定，最坏情况下为 (O(V))。

1.3 应用场景

BFS主要用于：

层次遍历：常用于树的层次遍历，可以按层依次访问树的节点。
最短路径问题：在无权图中，BFS 可以用来找到从起始节点到目标节点的最短路径。
社交网络中的好友推荐：可以通过 BFS 找到距离用户一定层次内的潜在好友。

DFS主要用于：

前中后序遍历：可用于树的遍历。
连通性检测：判断图中两个节点是否连通，或者找出图的所有连通分量。
拓扑排序：在有向无环图（DAG）中进行拓扑排序，用于确定任务的执行顺序。
求解迷宫问题：通过 DFS 尝试所有可能的路径，找到从起点到终点的路径。

2. 应用

2.1 BFS实现层次遍历

BFS伪代码如下：

1 创建一个队列Q，将起始节点s加入队列Q中。
2 当队列Q非空时，从队列Q中取出一个节点n。
3 如果节点n为目标节点，则找到了解，结束搜索。
4 否则，将节点n的未被访问过的邻居节点加入队列Q中。
5 重复步骤2~4，直到找到解或队列Q为空。

下边我们用BFS实现二叉树层次遍历：

public List<List<Integer>> levelShow(TreeNode root){
	List<List<Integer>> data = new ArrayList<>();
	// 空处理
	if(root == null){
		retrun data;
	}
	// 定义队列维护访问顺序
	Deuqe<TreeNode> queue = new LinkedListed<>();
	// 头节点入队
	queue.offer(root);
	while(!queue.isEmpty()){
		// 循环遍历完每一层级后再继续
		int size = queue.size();
		List<Integer> levelData = new ArrayList<>();
		for(int i = 0;i<size;i++){
			// 出队存储
			TreeNode node = queue.poll();
			// 防止空节点
			if(node == null){
				continue;
			}
			levelData.add(node.val);
			// 左节点入队
			if(root.left != null){
				queue.offer(root.left);
			}
			if(root.right != null){
				queue.offer(root.right);
			}
		}
		data.add(levelData);
	}
	retrun data;
} 

2.2 DFS实现前序遍历

DFS伪代码如下：

1 创建一个堆栈S，将起始节点s加入堆栈S中。
2 当堆栈S非空时，弹出堆栈S的栈顶元素top。
3 如果弹出元素是目标节点，则找到了解，结束搜索。
4 否则，将top的未被访问过的邻居节点加入堆栈S中。
5 重复步骤2~4，直到找到解或堆栈S为空。

下边我们用DFS实现二叉树前序遍历：

public List<Integer> frontShow(TreeNode root){
	List<Integer> data = new ArrayList<>();
	// 空处理
	if(root == null){
		retrun data;
	}
	// 定义栈维护访问顺序
	Stack<TreeNode> stack = new Stack<>();
	// 头节点入栈
	stack.push(root);
	while(!stack.isEmpty()){
		TreeNode node = stack.pop();
		// 防止空节点
		if(node == null){
			continue;
		}
		data.add(node.val);
		// 左节点入栈
		if(root.left != null){
			data.push(root.left);
		}
		if(root.right != null){
			data.push(root.right);
		}
	}
	retrun data;
} 

3. 总结

要理解BFS和DFS只需要熟记核心的一点：队列实现BFS，栈实现DFS。