高效查找节点最顶层祖先的算法：支持O(1)查询（需预处理）

在分类、标签这类存在父子层级关系的节点场景中，比如给定以下示例数据：

{ id: 1, name: 'Sports', parent_id: null }
{ id: 2, name: 'Fruits', parent_id: null }
{ id: 3, name: 'Citrus', parent_id: 2 }
{ id: 4, name: 'Orange', parent_id: 3 }
{ id: 5, name: 'Hockey', parent_id: 1 }

其层级关系为：

Sports -> Hockey
Fruits -> Citrus -> Orange

要实现O(1)时间复杂度查询任意节点的最顶层父节点，可以通过带路径压缩的预处理算法来完成，核心思路是一次性遍历所有节点，将每个节点直接关联到其顶层父节点并缓存，后续查询直接读取缓存结果即可。

具体实现步骤 #

1. 构建父节点映射表：先把所有节点的id和parent_id存入字典，方便快速查找父节点。
2. 带路径压缩的根节点查找：对每个节点，递归或迭代找到其顶层父节点，同时将路径上的所有节点直接指向顶层父节点（路径压缩），并把每个节点的顶层父节点存入缓存字典。

代码示例（JavaScript） #

递归实现（带路径压缩）

// 示例节点数据
const nodes = [
  { id: 1, name: 'Sports', parent_id: null },
  { id: 2, name: 'Fruits', parent_id: null },
  { id: 3, name: 'Citrus', parent_id: 2 },
  { id: 4, name: 'Orange', parent_id: 3 },
  { id: 5, name: 'Hockey', parent_id: 1 }
];

// 存储每个节点的父节点
const parentMap = {};
// 缓存每个节点的顶层父节点
const rootMap = {};

// 初始化父节点映射
nodes.forEach(node => {
  parentMap[node.id] = node.parent_id;
});

// 查找顶层父节点并进行路径压缩
function findRoot(id) {
  // 当前节点是顶层父节点
  if (parentMap[id] === null) {
    rootMap[id] = id;
    return id;
  }
  // 已缓存根节点，直接返回
  if (rootMap[id]) return rootMap[id];
  // 递归查找父节点的根，并将当前节点直接指向根（路径压缩）
  const root = findRoot(parentMap[id]);
  parentMap[id] = root;
  rootMap[id] = root;
  return root;
}

// 预处理所有节点
nodes.forEach(node => findRoot(node.id));

// O(1)查询示例：Orange的顶层父节点是Fruits（id=2）
console.log(rootMap[4]); // 输出：2

迭代实现（避免递归栈溢出）

如果节点层级极深，递归可能导致栈溢出，推荐用迭代方式实现路径压缩：

function findRoot(id) {
  let current = id;
  // 第一步：找到当前节点的顶层父节点
  while (parentMap[current] !== null) {
    current = parentMap[current];
  }
  const root = current;

  // 第二步：路径压缩，将当前节点到根节点路径上的所有节点直接指向根
  current = id;
  while (parentMap[current] !== root) {
    const nextParent = parentMap[current];
    parentMap[current] = root;
    rootMap[current] = root;
    current = nextParent;
  }
  rootMap[id] = root;
  return root;
}

复杂度说明 #

• 预处理阶段：由于路径压缩的存在，每个节点最多被访问两次（第一次查找路径，第二次更新父节点指向根），整体时间复杂度近似O(n)（n为节点数量）。
• 查询阶段：直接读取rootMap中的缓存值，时间复杂度为O(1)。

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