广度优先搜索：求解《429. N 叉树的层序遍历》和 《675. 为高尔夫比赛砍树》

思路

广度优先搜索，使用队列，先进先出

• 只有迭代写法，递归本质上是函数调用栈，无法用递归模拟广度优先搜索
• 队列初始项，通常根节点，当根节点可能为null / 题目数据范围中的节点数可能为0时
  • 优先判断空节点，返回结果

代码

广度优先搜索 · 层序遍历 · 出队

const dfs = root => {
  if (root === null) return []
  const queue = [root], r = []
  while (queue.length) {
    const n = queue.shift()
    r.push(n.val)
    if (n.left) queue.push(n.left)
    if (n.right) queue.push(n.right)
  }
  return r
}

广度优先搜索 · 移动指针 · 不出队

数据较多时，可以提高性能

• 因为 JavaScript 队列借助数组实现
• shift不仅要弹出元素，还要重新索引数组，性能开销较大

const dfs = root => {
  if (root === null) return []
  const queue = [root], r = []
  let index = 0
  while (index < queue.length) {
    const n = queue[index++]
    r.push(n.val)
    if (n.left) queue.push(n.left)
    if (n.right) queue.push(n.right)
  }
  return r
}

广度优先搜索 · 深度 / 层次 / 距离

适用于利用广度优先搜索，求深度 / 层次 / 距离的问题

const dfs = root => {
  if (root === null) return 0
  const queue = [root]
  let deepth = -1
  while (queue.length) {
    let l = queue.length
    deepth++
    while (l--) {
      const n = queue.shift()
      if (n.left) queue.push(n.left)
      if (n.right) queue.push(n.right)
    }
  }
  return deepth
}

以上三种代码可作为模板，可以组合使用

例题

429. N 叉树的层序遍历

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

答案

var levelOrder = function(root) {
  if (root === null) return []
  const queue = [root], r = []
  while (queue.length) {
    let l = queue.length
    r.push([])
    while (l--) {
      const n = queue.shift()
      r[r.length - 1].push(n.val)
      for (let i = 0; i < n.children.length; i++) {
        queue.push(n.children[i])
      }
    }
  }
  return r
};

675. 为高尔夫比赛砍树

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中： 0 表示障碍，无法触碰 1 表示地面，可以行走 比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度 每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。 你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。 你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。 可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

答案

1. 有树的点放入新数组，按树的高度升序排列
2. (0,0)及有序数组中，两两距离累加，广度优先搜索求距离

var cutOffTree = function (forest) {
  const m = forest.length, n = forest[0].length
  const forests = []
  for (let i = 0; i < m; i++) 
    for (let j = 0; j < n; j++) 
      if (forest[i][j] > 1) forests.push([i, j, forest[i][j]])
  forests.sort((a, b) => a[2] - b[2])
  let minStep = 0
  for (let i = 0; i < forests.length; i++) {
    const step = getStep(forests[i - 1] || [0, 0], forests[i], m, n, forest)
    if (step === -1) return -1
    minStep += step
  }
  return minStep
};
const getStep = ([x1, y1], [x2, y2], m, n, forest) => {
  const dr = [[-1, 0], [1, 0], [0, -1], [0, 1]]
  const queue = [[x1, y1]], visited = Array.from({length: m}, _ => new Uint8Array(n))
  let deepth = -1, index = 0
  while (index < queue.length) {
    let l = queue.length
    deepth++
    while (index < l) {
      const [x, y] = queue[index++]
      if (x === x2 && y === y2) return deepth
      for (let i = 0; i < 4; i++) {
        const [dx, dy] = dr[i]
        const xNew = x + dx, yNew = y + dy
        if (xNew < 0 || xNew >= m || yNew < 0 || yNew >= n) continue
        if (forest[xNew][yNew] === 0) continue
        if (visited[xNew][yNew]) continue
        visited[xNew][yNew] = 1
        queue.push([xNew, yNew])
      }
    }
  }
  return -1
}