深度优先搜索的概念原理 模板和leetcode刷题推荐(js)

概念

深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

我的理解为：深度优先搜索就是一步一步的递归，递归到底，就返回上一步，进行其他方向的递归，每个结点只能递归一次。然后挑出符合答案的递归形式，适合于解决找到最短回家的路，二叉树的最大深度等，具有单一极限的答案的题。

注意：

把自己放在其中一层去考虑如何递归，找出能递归全部节点的方法。在递归的过程中剔除掉不符合要求的方向，实现尽可能少的递归次数，节约时间空间。

模板

LeetCode104.二叉树的最大深度

var maxDepth = function(root) {//如果root==null，那当前树的深度就是0if (root == null) {return 0;} else {//递归左右子树最大深度var leftDepth = maxDepth(root.left);var rightDepth = maxDepth(root.right);return Math.max(leftDepth,rightDepth)+1;//当前树的根节点高度为1}};

刷题巩固

100相同的树 https://leetcode-/problems/same-tree

112路径总和 https://leetcode-/problems/path-sum

如果觉得《深度优先搜索的概念原理 模板和leetcode刷题推荐(js)》对你有帮助，请点赞、收藏，并留下你的观点哦！