09 极客大学-算法训练营-覃超-第九课.pdf

9、深度优先搜索、广度优先搜索的实现和特性 - 图1

参考链接

  • DFS 代码模板（递归写法、非递归写法）

    1. //JavaScript
    2. const visited = new Set()
    3. const dfs = node => {
    4. if (visited.has(node)) return
    5. visited.add(node)
    6. dfs(node.left)
    7. dfs(node.right)
    8. }

  • BFS 代码模板

    1. //JavaScript
    2. const bfs = (root) => {
    3. let result = [], queue = [root]
    4. while (queue.length > 0) {
    5.   let level = [];
    6.   let n = queue.length;
    7.   for (let i = 0; i < n; i++) {
    8.     let node = queue.pop()
    9.     level.push(node.val) 
    10.     if (node.left) queue.unshift(node.left)
    11.     if (node.right) queue.unshift(node.right)
    12.   }
    13.   result.push(level)
    14. }
    15. return result
    16. };

    实战题目

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

  • 最小基因变化
  • 括号生成（字节跳动、亚马逊、Facebook 在半年内面试中考过）

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

    课后作业

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

  • 单词接龙 II （微软、亚马逊、Facebook 在半年内面试中考过）
  • 岛屿数量（近半年内，亚马逊在面试中考查此题达到 350 次）
  • 扫雷游戏（亚马逊、Facebook 在半年内面试中考过）