从二叉树遍历深入理解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。