理解

DFS（deep-first-search 深度优先遍历）和 BFS（breath-first-search 广度优先遍历）都是常见的搜索算法。往往和递归、遍历、回溯的概念相关联。我把这两种搜索过程，形象描述成以下两个场景：

• 深度优先的过程符合我们生活中的寻路逻辑，因为它有一条直观的路径。就像我们迷宫探险，边走边在路上放上石子，走到尽头，就往回找到最近一个没有石子标记的交叉路继续探险，重复这个过程直到到达终点或者路已经走完。
• 广度优先可以简单理解为孙悟空的法外分身 —— 即拔毫毛一把，叫声：“变！”就能变出千百个分身，投入战斗。我们在每个交叉路口都变出相应的分身进行探险，同样将走过的路径用石子进行标记，如果所有分身都没找到路径说明迷宫无解，如果有一个分身到达终点即成功。

解题技巧

通过一道题来理解队列和堆栈是怎样应用的

假设我们有以下数据结构：

const data = {
  value: 0,
  children: [
    {
      value: 1,
      children: [
        {
          value: 11,
          children: [],
        },
        {
          value: 12,
          children: [],
        },
      ],
    },
    {
      value: 2,
      children: [
        {
          value: 21,
          children: [],
        },
        {
          value: 22,
          children: [],
        },
      ],
    },
  ],
};

我们先思考下几个问题：

• ? 深度优先遍历的结果是？
• ? 广度优先遍历的结果是
• ? 使用递归如何完成？
• ? 使用迭代如何完成？

具体可查看我上一篇文章 JS树形结构处理 | 七日打卡

练习题

leetcode 103二叉树的锯齿形层次遍历

var zigzagLevelOrder = function (root) {
    let ans = [];
    traverse(root, 0);
    return ans;
    function traverse(root, level) {
        if (!root) {
            return;
        }
        if (ans.length <= level) {
            ans.push([]);
        }
        if (level % 2 === 0) {
            ans[level].push(root.val)
        } else {
            ans[level].unshift(root.val)
        }
        traverse(root.left, level + 1);
        traverse(root.right, level + 1);
    }
};

leetcode 199二叉树的右视图

var rightSideView = function (root) {
  if (!root) {
    return [];
  }
  let queue = [root],
    level = undefined,
    result = [];
  while (queue.length) {
    level = undefined;
    rest = [];
    while (queue.length) {
      let peek = queue.shift();
      if (peek) {
        if (level === undefined) {
          level = peek.val;
        }
        if (peek.right) {
          rest.push(peek.right);
        }
        if (peek.left) {
          rest.push(peek.left);
        }
      }
    }
    result.push(level);
    queue.push(...rest);
  }
  return result;
};

leetcode 542. 01 矩阵

var updateMatrix = function (matrix) {
  const MAX_Y = matrix.length;
  const MAX_X = matrix[0].length;
  const isReachable = (point) => {
    return !(
      point[0] < 0 ||
      point[0] >= MAX_X ||
      point[1] < 0 ||
      point[1] >= MAX_Y
    );
  };
  let queue = [],
    distance = 0;
  function bfs(point) {
    if (matrix[point[1]][point[0]] === 0) {
      return 0;
    }
    queue = [point];
    distance = 0;
    outer: while (queue.length) {
      let rest = [];
      while (queue.length) {
        let peek = queue.shift();
        let x = peek[0];
        let y = peek[1];
        if (matrix[y][x] === 0) {
          break outer;
        }
        if (isReachable([x - 1, y])) {
          rest.push([x - 1, y]);
        }
        if (isReachable([x, y - 1])) {
          rest.push([x, y - 1]);
        }
        if (isReachable([x + 1, y])) {
          rest.push([x + 1, y]);
        }
        if (isReachable([x, y + 1])) {
          rest.push([x, y + 1]);
        }
      }
      distance++;
      queue.push(...rest);
    }
    return distance;
  }
  return matrix.map((row, y) => row.map((col, x) => bfs([x, y])));
};

前期回顾

Leetcode303 区域和检索 | 刷题打卡

LeetCode 组合总和三连 | 刷题打卡

LeetCode 703 数据流中的第 K 大元素 | 刷题打卡

LeetCode 239 滑动窗口最大值 | 刷题打卡

LeetCode 242 有效的字母异位词 | 刷题打卡

LeetCode 15 三数之和 | 刷题打卡

LeetCode 98 验证二叉搜索树 | 刷题打卡

LeetCode 50. Pow(x, n) | 刷题打卡

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情