BFS

回溯算法的框架：

var BFS = function(start, target) {
    var q = []; // 核心数据结构
    var visited = new Set(); // 避免走回头路
    var step = 0;
    
    q.push(start); // 将起点加入队列
    visited.add(start);

    while (q.length > 0) {
        var sz = q.length;
        /* 将当前队列中的所有节点向四周扩散 */
        for (var i = 0; i < sz; i++) {
            var cur = q.shift();
            /* 划重点：这里判断是否到达终点 */
            if (cur == target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            var adj = cur.adj();
            for (var j = 0; j < adj.length; j++) {
                var x = adj[j];
                if (!visited.has(x)) {
                    q.push(x);
                    visited.add(x);
                }
            }
        }
        step++;
    }
    // 如果走到这里，说明在图中没有找到目标节点
}

1.N 叉树的层序遍历 (opens new window)

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  let res = []
  if (!root) return res

  let queue = []
  queue.push(root)

  while (queue.length > 0) {
    let size = queue.length
    let data = []

    for (let i = 0; i < size; i++) {
      let cur = queue.shift()
      data.push(cur.val)
      if (cur.children) {
        for (let ch of cur.children) {
          queue.push(ch)
        }
      }
    }

    res.push(data)
  }

  return res
};

2.打开转盘锁 (opens new window)

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

 

示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:

输入: deadends = ["8888"], target = "0009"
输出：1
解释：把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：无法旋转到目标数字且不被锁定。
 

提示：

1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target 不在 deadends 之中
target 和 deadends[i] 仅由若干位数字组成

/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function (deadends, target) {
    // 记录需要跳过的死亡密码
    let deads = new Set(deadends);
    // for (let i = 0; i < deadends.length; i++) {
    //   deads.add(deadends[i])
    // }

    // 记录已经穷举过的密码，防止重复访问
    let visited = new Set();

    // BFS核心队列
    let q = [];

    // 从起点开始BFS
    let step = 0;
    q.push('0000');
    visited.add('0000');

    while (q.length > 0) {
      let sz = q.length;
      // 将当前队列中的所有的节点向四周扩散
      for (let i = 0; i < sz; i++) {
        let cur = q.shift();

        // 此路不通
        if (deads.has(cur)) {
          continue;
        }
        // 判断是否到达终点
        if (cur === target) {
          return step;
        }

        // 将一个节点的未遍历相邻节点加入队列
        for (let j = 0; j < 4; j++) {
          let up = plusOne(cur, j);
          if (!visited.has(up)) {
            q.push(up);
            visited.add(up);
          }

          let down = minusOne(cur, j);
          if (!visited.has(down)) {
            q.push(down);
            visited.add(down);
          }
        }
      }
      step++;
    }
    return -1
  };

// 将s[i]向上拨动一次
var plusOne = function (s, j) {
  let arr = s.split('');
  if (arr[j] === '9') {
    arr[j] = '0'
  } else {
    arr[j] = +arr[j] + 1 + '';
  }

  return arr.join('')
}

// 将s[i]向下拨动一次
var minusOne = function (s, j) {
  let arr = s.split('');
  if (arr[j] === '0') {
    arr[j] = '9'
  } else {
    arr[j] = +arr[j] - 1 + '';
  }

  return arr.join('')
}