如何从嵌套子节点数组树中筛选最高层级的区域节点？

我手头有一套带层级嵌套结构的区域数组，现在需要实现一个功能：给定一组节点key的输入数组，返回其中最高层级的区域节点。具体规则通过几个示例明确：

• 输入[7, 1, 10] → 返回[10]：因为10是1和7的父节点，子节点需要被剔除，只留最顶层的父节点
• 输入[1, 2] → 返回[1, 2]：二者属于同一层级，互相没有父子关系，所以全部保留
• 输入[2, 3, 1] → 返回[2, 1]：3是1的子节点，所以移除3；2和1无父子关联，保留
• 输入[1, 4] → 返回[1, 4]：二者层级不同但没有父子关系，全部保留

本质上就是把输入数组里所有「有祖先节点也在输入数组中」的子节点全部移除，剩下的就是我们要的最高层级节点。要实现这个逻辑，关键是先搞清楚每个节点的所有祖先节点，再逐一判断输入中的节点是否需要保留。

先假设你的区域数组结构是这样的（根据示例推断的结构，你可以根据实际结构调整）：

const regions = [
  {
    key: 10,
    name: 'Egypt',
    children: [
      { key: 1, name: 'Zone 1', children: [{ key: 3, name: 'Area 3' }] },
      { key: 2, name: 'Zone 2' },
      { key: 7, name: 'Zone 7' }
    ]
  },
  {
    key: 4,
    name: 'Another Region'
  }
];

第一步：构建节点的祖先映射表 #

我们需要先遍历整个区域数组，给每个节点记录它的所有祖先节点key：

const nodeAncestors = new Map();

// 递归遍历嵌套结构，填充映射表
function buildAncestorMap(node, currentAncestors = []) {
  // 给当前节点记录所有祖先
  nodeAncestors.set(node.key, new Set(currentAncestors));
  // 如果有子节点，继续递归，把当前节点加入子节点的祖先列表
  if (node.children) {
    const updatedAncestors = [...currentAncestors, node.key];
    node.children.forEach(child => buildAncestorMap(child, updatedAncestors));
  }
}

// 初始化映射表
regions.forEach(rootNode => buildAncestorMap(rootNode));

第二步：过滤出最高层级节点 #

有了祖先映射表，就可以对输入数组进行过滤了：

function getTopLevelNodes(inputKeys) {
  const inputKeySet = new Set(inputKeys);
  // 只保留那些「输入数组里没有它的任何祖先」的节点
  return inputKeys.filter(key => {
    const ancestors = nodeAncestors.get(key);
    // 检查祖先集合和输入集合是否有重叠
    return !Array.from(ancestors).some(ancestor => inputKeySet.has(ancestor));
  });
}

把示例输入放进去测试，结果完全符合预期：

console.log(getTopLevelNodes([7, 1, 10])); // 输出: [10]
console.log(getTopLevelNodes([1, 2])); // 输出: [1, 2]
console.log(getTopLevelNodes([2, 3, 1])); // 输出: [2, 1]
console.log(getTopLevelNodes([1, 4])); // 输出: [1, 4]

如果你的区域数组结构和示例不一样（比如子节点字段不是children，key字段叫别的名字），只需要修改buildAncestorMap函数里的遍历逻辑即可，核心判断逻辑不需要动。

内容的提问来源于stack exchange，提问作者Hussein Mohamed