评论数组快速归类的方法

[hoythan]

我有一批评论,他们的格式类似

[
    {
    	commentID:1,
        comment_parentID:0
    },
   {
    	commentID:2,
        comment_parentID:1
    },
   {
    	commentID:3,
        comment_parentID:0
    },
   {
    	commentID:4,
        comment_parentID:2
    },
   {
    	commentID:5,
        comment_parentID:1
    }
]

所有层级的评论都被平铺开来为一层,现在我要变为多层的

[
    {
        commentID:1,
        comments:[
            {
                commentID:2,
                comment_parentID:1,
                comments:[
                    {
                        commentID:4,
                        comment_parentID:2
                    },
                 ]
            },
            {
                commentID:5,
                comment_parentID:1
            }
        ]
        
    },
    {
    	commentID:3,
        comment_parentID:0
    }
]

如何循环才能最快,他们的顺序不一定是正序到倒叙,是有可能乱的. ID 是唯一的.

[lhx2008]

标题有歧义啊

[chairuosen]

先写个 map id=>obj 方便查找
然后遍历原始数据每一项如果有父级找到父级对象塞 children 里，然后再把根节点拎出来排个序就行
大概是两遍循环

[hoythan]

@chairuosen 他有多层

[cuebyte]

双向链表，由子找父

[hoythan]

@cuebyte 不懂...求教育

[geelaw]

/* in-place, destructive */
function treefy(inputArray)
{
var outputArray = [];
inputArray.forEach(function (comment) { comment.comments = []; });
inputArray.sort(function (a, b) { return a.commentID - b.commentID; });
var helper = function (begin, end, n)
{
if (begin >= end) return null;
var mid = (begin + end) >> 1;
var testee = outputArray[mid].commentID;
return testee < n ? helper(begin, mid, n) : testee > n ? helper(mid + 1, end, n) : outputArray[mid];
};
inputArray.forEach(function (comment)
{
if (comment.comment_parentID == 0) outputArray.push(comment);
else helper(0, inputArray.length, comment.comment_parentID).comments.push(comment);
});
return outputArray;
}

没有测试过, provided as-is.

[geelaw]

@geelaw 果然写错了，二分查找的部分应该是 inputArray。另外实际上可以用 sparse array 来做这件事情，不需要二分查找。

[cuebyte]

@hoythan 不知道为什么你 at 我我没看到，就是字面意思啊。

首先对评论排序，方便之后的二分查找。遍历列表，取出一个评论就找它的父评论，再由父评论找父父评论，都存到双向列表里，直到没有父评论，结束，再继续从评论列表里取。

等评论列表空了之后，就找那些顶级评论(root)，遍历其子评论树。最后得到你想要的。