前言
在日常的算法中,dfs,bfs常常用来够解决图论的问题,二叉树是图的子集,因而同样适用以下两种搜索思想,前端er难免会和树形结构打交道,本文通过树形结构与dfs,bfs相结合来解释我所理解的dfs和bfs
DFS和栈 BFS和队列
DFS(深度优先搜索):沿着根节点递归下去,遇到叶子节点则向上回溯
BFS (广度优先搜索):按照二叉树的层次访问,通常采用队列保存每个层次的节点。
广度优先遍历 又称为"宽度优先搜索"或"横向优先搜索",简称 BFS。它的实现思想是:从一点出发,查出它的邻接节点放入队列并标记,然后从队列中弹出第一个节点,寻找它的邻接未被访问的节点放入队列,直至所有已被访问的节点的邻接点都被访问过;若图中还有未被访问的点,则另选一个未被访问的点出发,执行相同的操作,直至图中所有节点都被访问。
举个🌰
上图就是典型的BFS广度优先搜索对于DFS
来说,大致流程可分为以下几步:
- 从初始点开始按照一个方向遍历,这个方向到尽头停止后到另一个方向,直到所有操作完成退出
- 深度优先搜索执行过程像是一个栈的操作。喜新厌旧。总是处理最新加入的节点,这点递归恰好满足其性质,并且递归代码写起来也更简洁。
- dfs的流程可以参考二叉树的前序遍历,它实质就是一个dfs。
举个🌰
BFS与DFS区别
bfs是浪费空间节省时间,dfs是浪费时间节省空间。 因为dfs要走很多的路径,可能都是没用的,(做有些题目的时候要进行剪枝,就是确定不符合条件的就可以结束,以免浪费时间,否则有些题目会TLE); 而bfs可以走的点要存起来,需要队列,因此需要空间来储存,便是浪费了空间,假设有十层,各个结点有2个子节点,那么储存到第10层就要存 2^10-1 个数据,而dfs只需要存10个数据,但是找到答案的速度相对快一点。
二叉树介绍
二叉树是将所有数据放在一个树形结构中,一个d层的二叉树可以储存的数据为(N = 2^d - 1)个数据,其查找和插入删除复杂度都为O(d) = O(log_2^N),算是对数组和链表的一种折中考虑。
二叉树的遍历
遍历指的是我们访问且不重复访问二叉树的所有结点。一般常用的有三种:前序遍历,中序遍历和后序遍历。简单介绍下:
- 先序遍历:先访问根节点,再访问左子结点,最后访问右子节点。上图的前序遍历为【8,3,1,6,4,7,10,14,13】
- 中序遍历:先访问左子结点,再访问根节点,最后访问右子结点。上图的中序遍历为【1,3,4,6,7,8,10,14,13】
- 后序遍历:先访问左子结点,再访问右子节点,最后访问根节点。上图的后序遍历为【1,4,7,6,3,13,14,10,8】对于后序遍历,注意根节点的左子树遍历完之后再去遍历右子树。
实战
简单的了解了DFS,BFS以及二叉树之后,我们可以通过实战来解释DFS,BFS在算法以及实际开发中的应用
1.路径总和
显然,利用DFS可以很轻松的解决此类问题
const pathSum = (root, sum) => {
let res = []
dfs(root, sum, res, [])
return res
}
function dfs(root, sum, res, arr) {
if (!root) return
arr.push(root.val)
if (!root.left && !root.right && root.val === sum) {
res.push([...arr])
}
dfs(root.left, sum - root.val, res, arr)
dfs(root.right, sum - root.val, res, arr)
arr.pop()
}
2.之字型打印二叉树
显然,此类题可以用BFS来解决let zigzagLevelOrder = (root) => {
if (!root) return []
let arr = [], res = [], depth = 1
arr.push(root)
while(arr.length !== 0) {
depth ++
let result = []
arr.forEach(item => {
result.push(item.val)
})
res.push(depth % 2 === 1 ? [...result].reverse() : [...result] )
let length = arr.length
for (let i = 0; i < length; i++) {
let node = arr.shift()
if(node.left){
arr.push(node.left);
}
if(node.right){
arr.push(node.right);
}
}
}
return res
};