[讨论/问答][Java]如何将树形结构转为扁平集合

[gaopinsong]

问题就如题。将树形结构转为扁平的集合。
想不用递归。或者其他高性能的实现方式。
最想的就是能用上 J8 最新的 Stream API 。
但是自己咋想也想不到比较靠谱的实现。
这里提供一个借口供大家举例。

class Node {
    private String name;
    private List<Node> children;
    // get set ignore
}

[msg7086]

不想用递归就把递归转换成队列或者栈。

[pynix]

遍历一遍，扔到列表去。

[yimity]

@pynix 遍历不得递归嘛？我还是用的递归

[yimity]

不过我貌似是存成扁平的然后遍历成树形

[linux40]

看见楼上都说遍历，我插一嘴，树的遍历只靠循环妥妥的。

[yuankui]

跟语言无关..

[yuankui]

楼主搜一下 深度优先 || 广度优先

[zhuangzhuang1988]

flatMap ??

[wizardoz]

深度优先用栈（其实用到栈就相当于递归），广度优先用队列。

[sleeperqp]

第一反应是并查集

[HypoChen]

bfs or dfs

[gaopinsong]

感谢大家的回复，今天也问了一个高端大学出来的同学，也是让我去搜
深度优先 || 广度优先
又学到了新的姿势。感谢各位的回复

[pke]

这个和 Dijkstra 算法有什么关系

[KotiyaSanae]

https://gist.github.com/SeavantUUz/74e91be581099e5536aa 把二叉树压成一个字符串（确实是扁平的集合），没有递归，因为是迭代实现的

[domty]

不用递归
用 while 循环加 stack 就可以了嘛
况且以我浅薄的经验来看
java 的尾递归调用在不适用 java8 的某些尾递归优化的特性的情况下 效率是弱于非递归调用的

[FrankFang128]

没人吐槽 J8...

[gaopinsong]

自己搞了个递归。对于 Java 针对尾递归的优化，不是很了解。回头去搜索下

private Stream<CategoryModel> flatTree(List<CategoryModel> categoryModels) {

Stream<CategoryModel> modelStream = categoryModels.stream();

for (CategoryModel categoryModel: categoryModels) {

List<CategoryModel> children = categoryModel.getChild();

if (children == null || children.size() < 1) continue;

modelStream = Stream.concat(modelStream, flatTree(children));
}

return modelStream;
}

调用的代码

Stream<CategoryModel> modelStream = flatTree(getCategoryTree());

return modelStream.collect(toList());

[gaopinsong]

自己搞了个递归。对于 Java 针对尾递归的优化，不是很了解。回头去搜索下

private Stream<CategoryModel> flatTree(List<CategoryModel> categoryModels) {
Stream<CategoryModel> modelStream = categoryModels.stream();
for (CategoryModel categoryModel: categoryModels) {
List<CategoryModel> children = categoryModel.getChild();
if (children == null || children.size() < 1) continue;
modelStream = Stream.concat(modelStream, flatTree(children));
}
return modelStream;
}

调用的代码

Stream<CategoryModel> modelStream = flatTree(getCategoryTree());
return modelStream.collect(toList());

[gaopinsong]

囧。。上边发的。咋没有代码格式。。。。还不能自己删除。囧啊