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

前言

在日常的算法中,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
};
原文链接:juejin.im

上一篇:使用GitHub Actions完成定时构建应用
下一篇:@segment/load-script

相关推荐

  • 队列的JS实现及广度优先搜索(BFS)的实现

    队列是先进先出(FIFO)的数据结构,插入操作叫做入队,只能添加在队列的末尾;删除操作叫做出队,只能移除第一个元素。在JS中,用数组可以很简单的实现队列。 以上就实现了队列的数据结构,那么队列这...

    2 年前
  • 用JS实现数据结构----排序二叉树

    排序二叉树 图片描述(https://img.javascriptcn.com/2443be17a2770dc93009b8dc8d3f8c62 "图片描述") 如上图为典型的排序二叉树,左孩子...

    2 年前
  • 构建二叉树进行数值数组的去重及优化

    构建二叉树进行数值数组的去重及优化 常见两层循环实现数组去重 通过 includes() map() 方法去重 通过 includes() reduce() 方法去重 ...

    2 年前
  • 最直白的告白-树的遍历BFS和DFS

    介绍:本篇用大白话来实现树的遍历,相信看完后“妈妈再也不用担心我的学习啦“!最近在力扣上刷算法题,觉得这么多年都白混了(啥也没记录下来)。名词解释:树的遍历方式总体分为两类:DFS: 深度优先搜索(d...

    17 天前
  • 数据结构总结(四)二叉树

    一、二叉树基础 高度、深度:是从零开始算的层:和深度一样,只是从一开始算完全二叉树:最后一层只允许缺右子节点的二叉树,如果不缺则是满二叉树存储方式: 链式存储法(常用) 数组。

    3 个月前
  • 坐下,这些都是二叉树的基本操作!

    本篇为复习过程中遇到过的总结,同时也给准备面试的同学一份参考。另外,由于篇幅有限,本篇的重点在于二叉树的常见算法以及实现。 常见的二叉树实现代码 之前写过相关的文章,是关于如何创建及遍历二叉树...

    2 年前
  • 动态规划练习题-加分二叉树

    动态规划练习题总(https://segmentfault.com/a/1190000020096944) 题目描述 设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2...

    10 个月前
  • 前端算法之遍历二叉树

    背景:二叉树是一种数据结构,那么如果使用js遍历它呢 1、前序遍历,根左右 2、中序遍历,左根右 3、后序遍历,左右根 4、js的二叉数结构 执行 结...

    2 个月前
  • 前端工程师的 LeetCode 之旅 -- 二叉树 Medium 篇(根据遍历序列构造二叉树)

    一、前言   上一篇中介绍了如何采用 DFS 和 BFS 的搜索思想去实现二叉树的前序遍历、中序遍历、后序遍历以及分层遍历。   这一节主要介绍 Medium 难度中比较常见的一种题型:根据各种...

    1 年前
  • 前端工程师的 LeetCode 之旅 -- 二叉树 Medium 篇(DFS 与 BFS)

    一、前言   Medium 难度主要考察结合二叉树性质的 CRUD 操作,而这一切的基础都离不开遍历二叉树。   二叉树是图的子集,因而同样适用以下两种搜索思想: DFS(深度优先搜索)...

    1 年前

官方社区

扫码加入 JavaScript 社区