无意中发现技术主管写的代码,大家帮忙看看什么水平?

虽然很多答主用了诸如“典范级”、“心旷神怡” 的形容, 赞美这段代码, 但这里, 出于技术讨论的动机, 我说说不同看法.

  1. 栈, 如果善于利用栈来处理树结构, 那么可以写出更简洁的代码, 根本不需要 recuresiveFn 这种方法.
  2. 泛型, 如果善于利用泛型, 那么可以写出更通用的代码,而不是耦合于某一种类型。
  3. 算法复杂度, 这段代码的时间复杂度是 N*N , 典型的暴力算法
  4. 代码结构, 写这段代码的人, 虽然有“拆分冗长逻辑为一个方法“ 的意识, 但是, 就其解决的问题而言, 代码可以更简洁.
  5. 命名,TreeUtil 是一个很“泛”的命名, 可是其内容中的 MenuTreeObject 却很“具体 ”, 两个 “域” 不匹配. (封面与内容不匹配)
  6. 灵性, 一段代码可以反映其作者在编写时的内心状态, 这位技术主管当时的状态应该不太好, 合理猜测公司加班情况比较严重.


这里给出我的代码方案, 第一版是时间复杂度 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); }

运行结果如下:

你可能想看:
标签: node写代码
分享给朋友: