求助：关于树的构建，还要加上分类

[NewConn]

有一个需求，小弟算法能力不强，不知道怎么实现
有一批平铺的数据，每个数据有 parentId ，Id ，type 等属性；按 node.parentId=parentNode.id 构建完之后是一棵树，然后统一挂在一个虚拟的根节点，也即真实数据是一级节点的 array
以上步骤都没有问题，难点在下面：
按数据的 type 进行分类，每个分类建立一个虚拟的树节点，统一挂在一个虚拟的根节点下；
type 的虚拟节点下的真实数据，也需要按父子关系把树构建出来，并且当前节点在树上到根节点也连带出来（向上时，如果节点数据不属于此 type ，也需要展示，此时加一个 readonly 标记）

我思考了如下方案：
（ 1 ）先把平铺的数据分类，每个分类下的 array 的每个元素进行构建树，但是如果两个节点(有如下可能：深度一样 /不一样；有 /没有父子关系)都在树的某个分支下，可能会构建出 2 棵树，且不好判断
（ 2 ）先构建树，然后提取符合特征的节点


这个问题把小弟难住了啊，不管怎么处理好像都不对

[sillydaddy]

真佩服我竟然读懂了。

用你说的第 2 种方案比较方便吧？从完整的树🌲里面，提取出每个 type 对应的子树：

```
function clipNode(node, type){
if(node.type != type && node.parent.type == type){
node.parent = null; //从 parent 中裁剪掉这个 node
}else{
clipNode(node.parent);//向 parent 递归
}
}

var leaf_nodes = node_has_no_children(all_nodes);
leaf_nodes.forEach((node)=>clipNode(node, "sometype"));

var new_leaf_nodes = node_has_no_children(all_nodes); //新的叶子节点，因为一些分支被裁剪掉了
var result = nodes_that_can_reach_root(new_leaf_nodes);
```


对所有的「叶子」节点向上递归，child->parent ，如果父节点属于 type ，而子节点不属于 type ，把子节点裁剪掉，中止这个路径的递归。

最后收集那些没有被裁剪掉的分支，即可以通过.parent.parent.parent...一直连接到虚拟 root 节点的叶子节点。这些叶子节点都属于没有被裁剪掉的分支。用这些叶子节点构造树🌲就是 type 对应的树。

[jjwjiang]

type 的虚拟节点下的真实数据，也需要按父子关系把树构建出来，并且当前节点在树上到根节点也连带出来（向上时，如果节点数据不属于此 type ，也需要展示，此时加一个 readonly 标记）

==> 没太明白，如果节点 type 不属于这个 type 也要展示而不是裁剪，那岂不是 type 的树就和原始树一样吗？

[NewConn]

@jjwjiang 只是向上递归到根节点，向下递归的子孙节点，如果没有这个 type 的就不展示

[NewConn]

@sillydaddy 谢谢，我研究下

[rrfeng]

不如说原始需求。

[NewConn]

@sillydaddy 老哥，功能可以解决，就是性能非常慢。
主要我的树的节点，只有父里面有一个 List<Node>存储子的对象的列表。这样的话，子就只能存父的 id ，而不能存对象，否则就会出现循环引用。所以每次裁剪的时候，都要在树上从上往下遍历。总体来看，需要 type 和 leaf_nodes 的 2 层循环，里面每次还需要从上往下遍历一次树(这个又是每级子节点的循环+每层的递归)。原始数据不多，却需要 30s

[NewConn]

@jjwjiang 按 1 楼老哥思路，我又梳理了一下。其实只裁剪一种情况：在树上从上向下，裁剪掉某个子树，这颗子树的所有节点都不属于 type 。

[sillydaddy]

@NewConn ， #7
是这样的，所以我贴在 1#楼的代码有问题啊。

不过 30s 有点难以想象，你的代码有几层循环啊？

根据你说的「原始数据不多」，可以考虑用空间换时间，比如要判断「子树的所有节点都不属于 type 」，可以为每个节点都保存一个用于判断「是否包含某个 type 」的数组：
type Node = {
...
children: Node[];
hasChildOfType : boolean[COUNT_OF_TYPES]; //NUM_OF_TYPES 是所有 type 的数量
};

然后给所有级别的父节点添加对应的标记：
all_nodes.forEach( node => {
node.hasChildOfType[node.type]=true;
node.parent.hasChildOfType[node.type]=true;
node.parent.parent.hasChildOfType[node.type]=true;
...
});

这样裁剪的时候再判断就省时间了。