从列表中嵌套项目的高效算法/递归函数

Question

我目前正在实施自己的评论系统。不幸的是 Disqus 或任何其他评论平台不符合我的要求。

我使用 NodeJS 和 MongoDB 作为后端。我需要运行基本上对我的数据库进行两个查询：

获取topic/slug
获取用户的所有评论

可以对主题发表评论或回复评论。

Hey, cool post # top lvl comment

Thanks! # reply to comment

Foo Bar! # reply to reply

and so on...

所以我的数据库模式看起来像

{
    id: ObjectId,
    text: string,
    author: { id: ObjectId, name: string },
    parent: nullable ObjectId,
    slug: string/number/whatever
}

如果parent为空，则为顶级评论，否则为回复。

到目前为止很简单，对吧？我现在遇到的问题是在帖子下方显示评论。当只有顶级评论时，这会很容易。只需获取一个特定 slug 的所有评论，按 date/rating/... 对它们进行排序，然后使用我的 HTML View Engine 进行编译。

但实际上有回复，我只是停留在需要组织结构的地方。我想将回复嵌套在我的列表中的评论中

原始列表（简化）

[
  { id: 1, text: 'foo', parent: null },
  { id: 2, text: 'bar', parent: 1 },
  // ...
]

预期输出

[
  { id: 1, text: 'foo', replies: [
    { id: 2, text: 'bar' },
  ] },
]

我已经尝试使用递归函数创建我的预期输出，但它变得非常奇怪。除非那样，否则效率不会很高。因此，由于我真的很沮丧，并且觉得没有解决这个问题有点愚蠢，所以我决定向您寻求帮助。

我想解决的实际问题：如何呈现我的评论，它们是否正确嵌套等
我要问的问题：如何有效地组织我的平面结构来解决上述问题？

Answer 1

这是一种线性复杂度的方法：

var comments = [{
  id: 3,
  text: 'second',
  parent: 1
}, {
  id: 1,
  text: 'root',
  parent: null
}, {
  id: 2,
  text: 'first',
  parent: 1
}, {
  id: 5,
  text: 'another first',
  parent: 4
}, {
  id: 4,
  text: 'another root',
  parent: null
}];

var nodes = {};

//insert artificial root node
nodes[-1] = {
  text: 'Fake root',
  replies: []
};

//index nodes by their id
comments.forEach(function(item) {
  if (item.parent == null) {
    item.parent = -1;
  }
  nodes[item.id] = item;
  item.replies = [];
});

//put items into parent replies
comments.forEach(function(item) {
  var parent = nodes[item.parent];
  parent.replies.push(item);
});

//root node replies are top level comments
console.log(nodes[-1].replies);

从列表中嵌套项目的高效算法/递归函数

Efficient algorithm / recursive function to nest items from a list

javascript

algorithm

nested

node.js