在家谱中查找最近共同祖先的算法？

Question

我有一些人这样反对：

{
  id: 444,
  ancestors: [
    { id: 142, father: 837, mother: 221, children: [ 844, 371, 473, 113 ] },
    // hundreds more ...
  ]
}

很容易找到两个或更多人之间的共同祖先：

const allAncestors = people.map(({ ancestors }) => ancestors).flat(1);
const commonAncestors = allAncestors.filter(({ id }) => {
  for (const person of persons) {
    if (!person.ancestors.find(ancestor => ancestor.id === id)) 
      return false;
  }
  return true;
});

但是我如何找到最近的共同祖先呢？我想已经在某个地方写了一个算法，但我所有的搜索都会带来与二叉树相关的结果（这没有用）。

Answer 1

确定“最近”含义的问题，因为任何拥有超过 2 个孩子的祖先对他们来说都是最近的，所以

建立家谱
找出哪些祖先有超过 2 个孩子。

const persons = [{
  id: 444,
  ancestors: [
    { id: 142 },
    { id: 143 },
    { id: 144 },
    // hundreds more ...
  ],
},{
  id: 445,
  ancestors: [
    { id: 133 },
    { id: 143 },
    // hundreds more ...
  ]
},{
  id: 446,
  ancestors: [
    { id: 142 },
    { id: 445 },
    // hundreds more ...
  ]
},
{
  id: 447,
  ancestors: [
    { id: 142 },
    { id: 445 },
    { id: 446 },
    // hundreds more ...
  ]
}]

const tree = {};
persons.forEach(p => p.ancestors.forEach(a => {
  const parent = tree[a.id] ??= {};
  parent[p.id] = tree[p.id] ??= {};
}));

const result = findCommon(tree);

console.log(...result);

function findCommon(tree, result = new Set){
  for(const id in tree){
    if(Object.values(tree[id]).length > 1){
      result.add(id);
    }
    findCommon(tree[id], result);
  }
  return result;
}