前语

近来前端已死的说法传的沸沸扬扬，尽管有些夸张，但也阐明晰现在前端工作形势并不达观。其实，不止是前端，本年各行各业都挺难的。而身处乱纪元的咱们，假如暂时还不能从千军万马中杀出重围，那就静下心来修习一下内功吧。

前端会算法究竟有没有用，这个只能说仁者见仁，智者见智。在我看来，算法其实是内功，在平时写事务代码的时分，不懂算法也能写，但是当面对一些杂乱需求的时分，或许就会比较懵，最终写出的代码很或许便是一堆的事务逻辑挤在一同，后期保护的时分就十分的费劲。而咱们假如懂一些算法，再面对这些需求的话，咱们会自然的对函数功用进行封装，会去考虑如何优化时刻杂乱度等等。

关于算法，我是从2021年开端佛系刷题的，现在日常周赛三题，偶然四题，尽管也不是什么大佬，但能够把我日常算法的经验和一些典型方法跟咱们分享一下。

这次首要介绍一下算法中比较常用的两种方法DFS和BFS。

DFS

DFS：深度优先遍历，顾名思义便是咱们在处理一个数据结构的时分是挑选一条线，一向走究竟，处理完结之后再回来处理第二条线。

如上图所示的树形结构，咱们是先处理树的左子节点，一向走到最底层节点，已经没有子节点了，才会回来处理倒数第二层数的右子节点。

举个比如：看一道力扣的简略题：

标题：给你两棵二叉树的根节点p和q，编写一个函数来查验这两棵树是否相同。假如两个树在结构上相同，并且节点具有相同的值，则以为它们是相同的。

例如：

输入： p = [1,2,3], q = [1,2,3]
输出： true

这儿标题中输入的p=[1,2,3],实际上内部转化的数据结构是这样的：

{
    val: 1,
    left: {
        val: 2,
        left: null,
        right: null
    },
    right: {
        val: 3,
        left: null,
        right: null
    }
}

关于这个题，咱们采用DFS的思路，便是先比较两棵树根节点是否相同，假如相同，咱们持续比较它的左子节点，假如左子节点相同，那么就持续往下进行，比较左子节点的左子节点，以此类推。当左子节点一路比较下来val值都是相同的话，那么咱们就回过头，走第二条线。在遍历的过程中一旦遇到节点val值不相等的情况，就不用再持续遍历，直接return false即可。

而这儿有两个要害点，也是DFS的要害点，假如咱们想比较整棵树是否相同，那咱们其实便是判别，，当时节点的val值是否相同，两棵树的左右子树是否相同，而比较左右子树是否相同，咱们同样能够用当时写的函数来去进行比较，也便是递归的调用自身；第二点，便是一定要记得写结束条件，咱们的深度遍历究竟要在什么情况下回头，不再持续往下遍历。

关于这个标题，咱们的结束条件便是：

p和q假如都是null的情况下，阐明这两个节点便是相同的，由于他们没有子节点了，这一条线路比较下来是ok的，能够return true；
p和q假如是一个为null,一个不会null，阐明这两个节点一定不相同，并且也不用再往下比较了，直接回来false即可；
而扫除以上两种情况之后，那么p,q就都是一个不为空的树，那此时咱们就能够比较p.val和q.val究竟是否相同，不相同，那么就直接回来false，假如相同，咱们持续递归调用函数，比较p.left和q.left以及p.right和q.right即可。

var isSameTree = function(p, q) {
    if(p == null && q == null) {
        return true
    }else if(p == null || q == null){
        return false
    }else if(p.val != q.val) {
        return false
    }else{
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
    }
};

上面这个题仅仅简略的了解了一下，究竟什么是DFS，以及DFS究竟要怎样用，接下来这道题或许就需求再多多思考一下了。

途径问题（标题难度：中等）

给你二叉树的根节点root和一个整数方针和targetSum，找出一切从根节点到叶子节点途径总和等于给定方针和的途径。

叶子节点是指没有子节点的节点。

输入： root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出： [[5,4,11,2],[5,8,4,5]]

依据标题剖析，咱们要求的是整个途径的和与targetSum的值相等，那么咱们这条途径便是一个有用的途径。用DFS来做的话，简略说便是从根节点开端一向走到叶子节点，假如这一条路走来一切节点val值之和等于targetSum那么这条途径咱们就能够放在答案数组中，假如不等，那么无事产生，不需求放进答案数组。

思路：

咱们能够思考，咱们要界说的这个dfs函数需求哪些参数
首先咱们要计算累加和，那就需求知道当时遍历到的节点的值是多少，拿到当时节点的信息，那么界说一个参数为tNode代表当时节点
然后由于咱们需求知道到叶子节点的时分前面节点的累加和，所以还需求一个参数sum
并且最终标题中要求，假如契合题意，那么回来的结果需求是一个一路走来一切val值组成的数组，那么咱们还需求一个记录途径的数组arr
至此，咱们的参数界说完结，这三个参数基本上能够满足咱们写dfs函数了

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function(root, targetSum) {
    function dfs(tNode,arr,sum) {}
};

开端编写dfs函数：

首先确认dfs函数结束条件：当咱们的节点是叶子节点的时分，进行判别，假如途径上val累加之和等于targetSum的话，咱们就将途径放在答案数组；假如不等，那么无事产生，阐明这条线并不是咱们要的答案，持续进行其他线即可。
假如不是叶子节点（也便是当时节点还有左子节点或许右子节点），那么咱们递归调用dfs函数，一同将累加和sum和途径数组arr处理之后传递下去。

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function(root, targetSum) {
    if(!root) return []
    var ans = []
    function dfs(tNode,arr,sum) {
        if(tNode.left == null && tNode.right == null) {
            if(sum + tNode.val == targetSum){
                ans.push([...arr,tNode.val])
                return
            }
        }else{
            if(tNode.left){
                dfs(tNode.left,[...arr,tNode.val],sum + tNode.val)
            }
            if(tNode.right){
                dfs(tNode.right,[...arr,tNode.val],sum + tNode.val)
            }
        }
    }
    dfs(root,[],0)
    return ans
};

这儿用打开运算符处理了dfs方法中的arr，是由于咱们在js中，数组的寄存方位是堆，而咱们每次传递的arr仅仅指向真实数组寄存方位的一个指针罢了，所以假如咱们一条线遍历完之后，没有再对咱们保护的arr进行处理的话，就会出现问题，所以这儿咱们用打开运算符，每次都处理成一个新数组。但这样就会导致，咱们每次都创立一个新数组向下传递，也便是说咱们每次都会拓荒新的空间去寄存数组，所以这儿咱们能够优化一下：

var pathSum = function(root, targetSum) {
    if(!root) return []
    var ans = []
    function dfs(tNode,arr,sum) {
        if(tNode.left == null && tNode.right == null) {
            if(sum + tNode.val == targetSum){
                ans.push([...arr,tNode.val])
                return
            }
        }else{
            if(tNode.left){
                arr.push(tNode.val)
                dfs(tNode.left,arr,sum + tNode.val)
                arr.pop()
            }
            if(tNode.right){
                arr.push(tNode.val)
                dfs(tNode.right,arr,sum + tNode.val)
                arr.pop()
            }
        }
    }
    dfs(root,[],0)
    return ans
};

在每次递归调用的时分，将当时节点的val推入数组，当咱们下面的线走完之后，将arr通过pop复原回原来的状态，再去处理另一条线路的节点。这样就不需求像原来那样不断的拓荒新数组了。

BFS

BFS：广度优先遍历，便是咱们在处理一个数据结构的时分，能够理解为是铺打开的，多条线一同进行，你走一步我也走一步，多条线路一同推动的算法。

如上图所示的树形结构，咱们一层一层的遍历，界说一个额外的数组queue来放置咱们需求处理的节点，只需当queue中的节点处理完之后，咱们再持续处理下一层的节点。

同样的标题：

标题：给你两棵二叉树的根节点p和q，编写一个函数来查验这两棵树是否相同。假如两个树在结构上相同，并且节点具有相同的值，则以为它们是相同的。

例如：

输入： p = [1,2,3], q = [1,2,3]
输出： true

假如咱们用BFS的解法来做也是能够的：

BFS的主体思维便是咱们每条线都要一步一步的走，那么咱们就能够创立一个数组queue来存储咱们接下来要遍历节点
然后咱们不断的从queue中取出咱们要遍历的节点，一同判别这个节点究竟是否契合咱们的要求，假如契合那么就将它的子节点推入一个备用数组tmp，假如不契合要求，那么能够直接中止遍历，return false

这儿由于是有两棵树，所以咱们能够创立两个数组queue1,queue2，一同创立两个备用数组tmp1,tmp2 每次遍历的时分，比较从两个queue中相同方位取出的节点，假如整棵树的节点都遍历结束之后，依然没有return false，那么就阐明一切节点都是契合要求的，那么return true即可；

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if(p == null && q == null) {
        return true
    }else if(p == null || q == null){
        return false
    }
    var queue1 = [p]
    var queue2 = [q]
    var tmp1 = []
    var tmp2 = []
    while(queue1.length != 0 || queue2.length != 0) {
        // 这儿假如两个queue的长度不一致，阐明同层的节点数目都是不一致的，必然不是相同的树
        if(queue1.length != queue2.length) return false
        for(var i = 0;i < queue1.length;i++) {
            if(queue1[i] == null && queue2[i] == null) {
                continue
            }else if(queue1[i] == null || queue2[i] == null) {
                return false
            }else  if(queue1[i].val != queue2[i].val) {
                return false
            }else{
                tmp1.push(queue1[i].left)
                tmp1.push(queue1[i].right)
                tmp2.push(queue2[i].left)
                tmp2.push(queue2[i].right)
            }
        }
        queue1 = tmp1
        queue2 = tmp2
        tmp1 = []
        tmp2 = []
    }
    return true
};

再看前面的这个途径问题

给你二叉树的根节点root和一个整数方针和targetSum，找出一切从根节点到叶子节点途径总和等于给定方针和的途径。

叶子节点是指没有子节点的节点。

输入： root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出： [[5,4,11,2],[5,8,4,5]]

这儿咱们尝试用BFS的思维来解题：

依据上一道标题的解法，咱们知道BFS的一个常用操作便是创立一个行列，用这个行列数组去存储接下来要去操作的节点，所以，这儿咱们同样界说一个使命行列的数组queue
然后咱们会遇到一个比较麻烦的问题，便是我要怎样知道每次累加到当时节点的时分，累加的和以及遍历过节点的数组是什么样的呢，否则到最终叶子节点的时分，咱们要怎样确认这条途径是不是咱们想要的答案呢？
为了解决咱们上面遇到的这两个问题，咱们能够创立一个Map，用来记录走到当时节点时，累加和(sum)是多少，途径(arr)是怎样的。而这种方法也是在算法中很常用的方法，叫哈希表，也不是什么高大上的东西，便是咱们前端日常运用的object，Map，都能够作为容器来运用。说直白点，便是找个当地用key – value的形式存储咱们的每个节点，这样当咱们要用的时分，随时取用。
整理一下上面的思路，便是咱们通过不断的从queue中取值，然后看这个节点有没有子节点，假如没有子节点，那么咱们就判别是否等于targetSum，等于就推入咱们的答案数组ans；
假如该节点不是叶子节点，那么就将这个节点的左子节点推入queue,右子节点推入queue，并将抵达对应节点时的累加和以及途径记录在Map中。
咱们能够尝试写一下，下面是我写的BFS解法，写完能够对照理一下思路

/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {number[][]}
 */
var pathSum = function(root, targetSum) {
    if(!root) return []
    var ans = []
    var queue = [root]
    var m = new Map()
    m.set(root, {
        sum: root.val,
        arr: [root.val]
    })
    while(queue.length) {
        let tNode = queue.shift()
        let x = m.get(tNode)
        if(tNode.left == null && tNode.right == null) {
            if(x.sum == targetSum) {
                ans.push(x.arr)
            }
        }else{
            if(tNode.left) {
                m.set(tNode.left, {
                    sum: x.sum + tNode.left.val,
                    arr: [...x.arr, tNode.left.val]
                })
                queue.push(tNode.left)
            }
            if(tNode.right) {
                m.set(tNode.right, {
                    sum: x.sum + tNode.right.val,
                    arr: [...x.arr, tNode.right.val]
                })
                queue.push(tNode.right)
            }
        }
    }
    return ans
};

最终

至此，咱们对DFS和BFS的运用方法有了一个简略的认识，并且在最终的标题中，还了解到了哈希表的用法，真实的掌握这些方法还是要多多练习。

DFS和BFS不仅仅是能够解决这种树形数据结构问题的方法，它们更是一种思维，DFS便是一条路一条路走究竟的试，BFS便是一切途径我先搜集，然后一同一步一步的走，这便是它们的实质。能够尝试看一下力扣中，机器人移动格子的问题，能够用动态规划的解法去做，但同样能够用DFS和BFS去做，有爱好的朋友能够去找找尝试一下。

前端乱纪元，修习一下内功——前端算法

前语

DFS

BFS

最终

作者信息

前端乱纪元，修习一下内功——前端算法

前语

DFS

BFS

最终

相关文章

携手共建云原生生态 阿里云云原生加速器第二次集结圆满结营

视野修炼-技术周刊第76期 | Rolldown 开源

Flutter基础之Json数据解析

WebGL高质量实时角色渲染

作者信息

携手共建云原生生态阿里云云原生加速器第二次集结圆满结营