无意中发现技术主管写的代码，大家帮忙看看什么水平?
虽然很多答主用了诸如“典范级”、“心旷神怡” 的形容, 赞美这段代码, 但这里, 出于技术讨论的动机, 我说说不同看法.
- 栈, 如果善于利用栈来处理树结构, 那么可以写出更简洁的代码, 根本不需要
recuresiveFn这种方法. - 泛型, 如果善于利用泛型, 那么可以写出更通用的代码，而不是耦合于某一种类型。
- 算法复杂度, 这段代码的时间复杂度是 N*N , 典型的暴力算法
- 代码结构, 写这段代码的人, 虽然有“拆分冗长逻辑为一个方法“ 的意识, 但是, 就其解决的问题而言, 代码可以更简洁.
- 命名,
TreeUtil是一个很“泛”的命名, 可是其内容中的MenuTreeObject却很“具体 ”, 两个 “域” 不匹配. (封面与内容不匹配) - 灵性, 一段代码可以反映其作者在编写时的内心状态, 这位技术主管当时的状态应该不太好, 合理猜测公司加班情况比较严重.
这里给出我的代码方案, 第一版是时间复杂度 O(N^2) 的版本
interface ITreeNode<T extends ITreeNode<T>> {
T parent();
void setChildren(List<T> children);
List<T> getChildren();
}
class TreeUtil {
public static <T extends ITreeNode<T>> List<T> listToTree(List<T> list) {
var roots = list.stream()
.filter(n -> n.parent() == null)
.collect(Collectors.toList());
var stack = roots.stream().collect(Collectors.toCollection(Stack::new));
while (!stack.isEmpty()) {
var node = stack.pop();
//每一个元素都需要跟其他所有元素比较,时间复杂度 N*N
node.setChildren(
list.stream()
.filter(n -> n.parent() != null)
.filter(n -> n.parent().equals(node))
.collect(Collectors.toList()));
node.getChildren().forEach(stack::push);
}
return roots;
}
}
第二版利用动态规划的思想, 分解出“自顶向下构建树”的子问题：“给定一个节点，其子节点有哪些”。
只需一次遍历，缓存每一个节点的 父子关系 ，即可得到每个节点，对于这个子问题的结果。
之后便可以自顶向下地构建树。 在构建过程中，每处理一个节点，都是直接从缓存取其子节点，没有重复计算（不需要重复访问不相关的节点），复杂度从平方级降为线性。
class TreeUtil {
public static <T extends ITreeNode<T>> List<T> listToTree2(List<T> list) {
//第一次遍历: 记录节点间的父子关系
var relations = new HashMap<T, List<T>>();
for (T node : list) {
List<T> relation = relations.computeIfAbsent(node.parent(), (p) -> new LinkedList<>());
relation.add(node);
}
var roots = relations.get(null); //父节点为null的即为根节点
//第二次遍历: 根据父子关系建立树
var stack = roots.stream().collect(Collectors.toCollection(Stack::new));
while (!stack.isEmpty()) {
T node = stack.pop();
node.setChildren(relations.getOrDefault(node, Collections.emptyList()));
stack.addAll(node.getChildren());
}
return roots;
}
}
下面是测试代码:
static class MenuItem implements ITreeNode<MenuItem> {
private Integer id;
private String name;
private Integer parentId;
public MenuItem(Integer id) {
this.id = id;
}
public MenuItem(Integer id, String name, Integer parentId) {
this.id = id;
this.name = name;
this.parentId = parentId;
}
@Getter
@Setter
private List<MenuItem> children;
@Override
public MenuItem parent() {
return parentId == null ? null : new MenuItem(parentId);
}
@Override
public boolean equals(Object o) {
return o instanceof MenuItem && Objects.equals(id, ((MenuItem) o).id);
}
@Override
public int hashCode() {
return Objects.hash(id);
}
}
public static void main(String[] args) {
List<MenuItem> menuList = Arrays.asList(
new MenuItem(1, "一级菜单", null),
new MenuItem(2, "二级菜单1", 1),
new MenuItem(3, "二级菜单2", 1),
new MenuItem(3, "三级菜单1", 2),
new MenuItem(4, "三级菜单2", 2)
);
List<MenuItem> menuTree = TreeUtil.listToTree2(menuList);
System.out.println(menuTree);
}
运行结果如下:
