DFS

DFS框架

  1. result = []
  2. def backtrack(路径, 选择列表):
  3.     if 满足结束条件:
  4.         result.add(路径)
  5.         return
  7.     for 选择 in 选择列表:
  8.         做选择
  9.         backtrack(路径, 选择列表)
  10.         撤销选择

例题1

46. 全排列 - 力扣（LeetCode） (leetcode-cn.com)
image-20210504092842700.png

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[][]}
  4.  */
  5.  Array.prototype.contains = function(num){
  6.     for(let i=0;i<this.length;i++){
  7.         if(this[i]===num){
  8.             return true;
  9.         }
  10.     }
  11.     return false;
  12. };
  13. var permute = function(nums) {
  14.     let res = [];
  15.     let track = [];
  16.     backtrack(nums,track);
  17.     return res;
  19.     function backtrack(nums,track){
  20.         if(nums.length===track.length){
  21.             let newTrack = [];
  22.             Object.assign(newTrack,track)
  23.             res.push(newTrack);
  24.             return;
  25.         }
  26.         for(let num of nums){
  27.             if(track.contains(num)){
  28.                 continue;
  29.             }
  30.             track.push(num);
  31.             backtrack(nums,track);
  32.             track.pop();
  33.         }
  34.     }
  35. };

例题2

78. 子集 - 力扣（LeetCode） (leetcode-cn.com)
image-20210504093621622.png
这个需要剪枝：
dfs2.png

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let res = [];
    let track = [];
    trackback(nums,track,0);
    return res;

    function trackback(nums,track,start){
        let newTrack = [];
        Object.assign(newTrack,track);
        res.push(newTrack);
        for(let i=start;i<nums.length;i++){
            track.push(nums[i]);
            trackback(nums,track,i+1)
            track.pop();
        }
    }
};

BFS

BFS框架

要说框架的话，我们先举例一下 BFS 出现的常见场景好吧，问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离，这个例子听起来很枯燥，但是 BFS 算法问题其实都是在干这个事儿

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路

    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

例题1

111. 二叉树的最小深度 - 力扣（LeetCode） (leetcode-cn.com)
求二叉树最小高度
image-20210504094011605.png

输入：root = [3,9,20,null,null,15,7]
输出：2

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function (root) {
    if (!root === true) {
        return 0;
    }
    let queue = [];
    let depth = 1;
    queue.push(root);
    while (queue.length !== 0) {
        // 踩坑：这里queue.length要另外写在外面，要是写在循环里是动态改变的，最终结果始终输出1
        let ql = queue.length;
        for (let i = 0; i < ql; i++) {
            let cur = queue.shift();
            if (cur.left === null && cur.right === null) {
                return depth;
            }
            if (cur.left !== null) {
                queue.push(cur.left);
            }
            if (cur.right !== null) {
                queue.push(cur.right);
            }
        }
        depth++;
    }
    return depth;
};