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

在树(图/状态集)中寻找特定结点。

  • 每个节点都会访问一次
  • 每个节点仅仅要访问一次
  • 对于节点的访问顺序不限
    • 深度优先: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]); } } }