最难不过二叉树--你应该知道的BFS与DFS

4,765 阅读4分钟

前言

在日常的算法中,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
};