前言

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

前端会算法到底有没有用，这个只能说仁者见仁，智者见智。在我看来，算法其实是内功，在平时写业务代码的时候，不懂算法也能写，但是当面对一些复杂需求的时候，可能就会比较懵，最后写出的代码很可能就是一堆的业务逻辑挤在一起，后期维护的时候就非常的吃力。而我们如果懂一些算法，再面对这些需求的话，我们会自然的对函数功能进行封装，会去考虑如何优化时间复杂度等等。

对于算法，我是从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去做，有兴趣的朋友可以去找找尝试一下。

其他