邻接表：深度优先搜索、广度优先搜索和拓扑排序求解最小高度树

310. 最小高度树

树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。 可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。 请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。 树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

答案

查找

• 找距离 0 的最远节点 right
• 找距离 right 的最远节点 left
• left 到 right 即树的最大距离，即树的最小高度

var findMinHeightTrees = function(n, edges) {
  const adj = Array.from({length: n}, _ => [])
  for (const [x, y] of edges) {
    adj[x].push(y)
    adj[y].push(x)
  }
  const parent = new Int16Array(n)
  const left = findLongestNode(0, adj, parent)
  let right = findLongestNode(left, adj, parent)
  const path = [], ans = []
  parent[left] = -1
  while (right !== -1) {
    path.push(right)
    right = parent[right]
  }
  const len = path.length
  if (len % 2 === 0) ans.push(path[(len >> 1) - 1])
  ans.push(path[len >> 1])
  return ans
};

找最远节点 findLongestNode 的实现：

• 广度优先搜索
  • 层层向外寻找

const findLongestNode = (n, adj, parent) => {
  const queue = [n], visited = new Set
  let longestNode = null
  while (queue.length) {
    const n = queue.shift()
    longestNode = n
    visited.add(n)
    const len = adj[n].length
    for (let i = 0; i < len; i++) {
      if (visited.has(adj[n][i])) continue
      parent[adj[n][i]] = n
      queue.push(adj[n][i])
    }
  }
  return longestNode
}

• 深度优先搜索
  • 需要记录层级（递归和迭代都可以）
  • 递归

const findLongestNode = (n, adj, parent) => {
  const visited = new Set
  let longestNode= null, maxDeepth = 0
  const d = (n, deepth) => {
    if (n === null) return
    if (deepth > maxDeepth) {
      maxDeepth = deepth
      longestNode = n
    }
    visited.add(n)
    const len = adj[n].length
    for (let i = 0; i < len; i++) {
      if (visited.has(adj[n][i])) continue
      parent[adj[n][i]] = n
      d(adj[n][i], deepth + 1)
    }
  }
  d(n, 0)
  return longestNode
}

• 迭代

const findLongestNode = (n, adj, parent) => {
  const queue = [[n, 0]], visited = new Set
  let longestNode = null, maxDeepth = 0
  while (queue.length) {
    const [n, deepth] = queue.pop()
    if (maxDeepth < deepth) {
      maxDeepth = deepth
      longestNode = n
    }
    visited.add(n)
    const len = adj[n]?.length
    for (let i = 0; i < len; i++) {
      if (visited.has(adj[n][i])) continue
      parent[adj[n][i]] = n
      queue.push([adj[n][i], deepth + 1])
    }
  }
  return longestNode
}

拓扑排序

从入度 为1的节点，广度优先遍历，层层减少入度，直到剩下不超过2个节点

var findMinHeightTrees = function(n, edges) {
  if (n === 1) return [0]
  const adj = Array.from({length: n}, _ => [])
  const degree = new Uint16Array(n)
  for (const [x, y] of edges) {
    adj[x].push(y)
    adj[y].push(x)
    degree[x]++
    degree[y]++
  }
  const queue = []
  for (let i = 0; i < n; i++) if (degree[i] === 1) queue.push(i)
  let remainNodes = n
  while (remainNodes > 2) {
    let l = queue.length
    remainNodes -= l
     while (l--) {
      const n = queue.shift()
      const len = adj[n].length
      for (let i = 0; i < len; i++) {
        if (--degree[adj[n][i]] === 1) queue.push(adj[n][i])
      }
    }
  }
  return queue
};