深度/广度 优先搜索的实现和特性

在树（图/状态集）中寻找特定结点。

• 每个节点都会访问一次
• 每个节点仅仅要访问一次
• 对于节点的访问顺序不限
  • 深度优先：depth first search
  • 广度优先：breadth first search

深度优先搜索

function dfs () {
  if (visited.has(node)) {
    // already visited
    return;
  }
  visted.add(node);
  // process current node
  dfs(node.left);
  dfs(node.right);
}

function dfs () {
  visted.add(node);
  // # process current node here.
  for (next_node in node.children()) {
    if (!visited.has(next_node)) {
      dfs(next_node, visited);
    }
  }
}

function dfs (tree) {
  if (!tree) return;
  visited, stack = [], [tree.root];
  while (stack.length) {
    node = stack.pop();
    visited.add(node);
    process(node);
    nodes = generate_related_nodes(node);
    stack.push(nodes);
  }
}

广度优先搜索

function bfs (graph, start, end) {
  queue = [[start]];
  visted.add(start);

  while (queue.length) {
    node  = queue.shift();

    visited.add(node);

    process(data);

    nodes = generate_related_nodes(node);

    queue.push(...nodes);
  }
}

相关题目

const dfs = (root) => {
  console.log(root.val);
  root.children.forEach(dfs);
}

const bfs = (root) => {
  const queue = [root];

  while (queue.length) {
    const n = queue.shift();

    console.log(n.val);

    n.children.forEach(child => {
      queue.push(child);
    });
  }
}

二叉树的层序遍历（字节跳动、亚马逊、微软在半年内面试中考过）

最小基因变化

括号生成（字节跳动、亚马逊、Facebook 在半年内面试中考过）

在每个树行中找最大值（微软、亚马逊、Facebook 在半年内面试中考过）

// 二叉树的层序遍历

// 1. bfs 
// 2. dfs

/**
 * bfs
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  if (!root) return [];

  const ans = [];

  const queue = [root];

  while (queue.length) {
    let len = queue.length;

    ans.push([]);

    while (len--) {
      const n =  queue.shift();

      ans[ans.length - 1].push(n.val);

      n.left && queue.push(n.left);
      n.right && queue.push(n.right);
    }
  }

  return ans;
};

/**
 * dfs
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  const ans = [];

  const dfs = (root, l) => {
    if (!root) return;

    if (!ans[l]) ans[l] = [];

    ans[l].push(root.val);

    dfs(root.left, l + 1);
    dfs(root.right, l + 1);
  }

  dfs(root, 0);

  return ans;
};

// 最小基因变化

/**
 * @param {string} start
 * @param {string} end
 * @param {string[]} bank
 * @return {number}
 */
var minMutation = function(start, end, bank) {
  const bankSet = new Set(bank);

  if (!bankSet.has(end)) return -1;

  const dna = ['A', 'C', 'G', 'T'];

  const queue = [[start, 0]];

  while (queue.length) {
    const [node, count] = queue.shift();

    if (node === end) return count;

    for (let i = 0; i < node.length; i++) {
      for (let j = 0; j < dna.length; j++) {
        const d = node.slice(0, i) + dna[j] + node.slice(i + 1);

        if (bankSet.has(d)) {
          queue.push([d, count + 1]);
          bankSet.delete(d);
        }
      }
    }
  }

  return -1;
};

// 括号生成

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  const ans = [];

  function helper (left, right, n, s) {
    if (left === n && right === n) {
      ans.push(s);
      return;
    }

    if (left < n) {
      helper(left + 1, right, n, s + '(');
    }
    if (left > right) {
      helper(left, right + 1, n, s + ')');
    }
  }

  helper(0, 0, n, '');

  return ans;
};

// 在每个树行中找最大值

/**
 * 广度优先遍历
 * @param {TreeNode} root
 * @return {number[]}
 */
var largestValues = function(root) {
  if (!root) return [];

  const queue = [root];
  const ans = [];

  while (queue.length) {
    let len = queue.length;

    ans.push(-Infinity);

    while (len--) {
      const n = queue.shift();
      const previous = ans[ans.length - 1];

      ans[ans.length - 1] = Math.max(previous, n.val);

      n.left && queue.push(n.left);
      n.right && queue.push(n.right);
    }
  }


  return ans;
};

单词接龙（亚马逊在半年内面试常考）

单词接龙 II （微软、亚马逊、Facebook 在半年内面试中考过）

岛屿数量（近半年内，亚马逊在面试中考查此题达到 350 次）

扫雷游戏（亚马逊、Facebook 在半年内面试中考过）

// 单词接龙

/**
 * 广度优先搜索
 * @param {string} beginWord
 * @param {string} endWord
 * @param {string[]} wordList
 * @return {number}
 */
const ladderLength = (beginWord, endWord, wordList) => {
  const words = new Set(wordList);
  const queue = [];

  queue.push([beginWord, 1]);

  while (queue.length) {
    const [word, level] = queue.shift();

    if (word == endWord) return level;

    for (let i = 0; i < word.length; i++) {
      for (let c = 97; c <= 122; c++) {
        const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);

        if (words.has(newWord)) {
          queue.push([newWord, level + 1]);
          words.delete(newWord);
        }
      }
    }
  }

  return 0;
};

// 岛屿数量

/**
 * 深度优先搜索
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
  let count = 0;

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === '1') {
        count++;
        trunZero(i, j, grid);
      }
    }
  }

  return count;
};

function trunZero (i, j, grid) {
  if (
    i < 0 || i >= grid.length ||
    j < 0 || j >= grid[0].length || grid[i][j] === '0'
  ) return;

  grid[i][j] = '0';

  trunZero(i, j + 1, grid);
  trunZero(i, j - 1, grid);
  trunZero(i + 1, j, grid);
  trunZero(i - 1, j, grid);
}


/**
 * 广度优先搜索
 * @param {character[][]} grid
 * @return {number}
 */
const numIslands = (grid) => {
  const queue = [];

  let count = 0;

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j] === '1') {
        count++;
        grid[i][j] = '0';
        queue.push([i, j]);
        turnZero(queue, grid);
      }
    }
  }

  return count;
}

function turnZero (queue, grid) {
  const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]];

  while (queue.length) {
    const cur = queue.shift();

    for (const dir of dirs) {
      const x = cur[0] + dir[0];
      const y = cur[1] + dir[1];

      if (
        x < 0 || x >= grid.length ||
        y < 0 || y >= grid[0].length ||
        grid[x][y] !== '1'
      ) continue;

      grid[x][y] = '0';

      queue.push([x, y]);
    }
  }
}