学而时习之集合与多线程篇: 玩转异形树结构

前言

3月的天, 阴沉沉, 灰蒙蒙, 如忆起往事时心底激荡起伏, 过后不经意间地洒下的几滴细雨. 在本适合出门踏青的周末, 张大胖选择了睡懒觉. 忽暗忽明的微光穿过门窗, 撒在他的大肚腩上, 抚慰着一周996过后的疲惫, 现已到半晌, 隔壁洗衣机的螺旋桨突然轰隆隆的转起来, 如一头见了红布的公牛样咆哮着. 这可打扰了大胖的美梦, 他强忍着睡意睁开双眼, 一时间昨晚难缠的需求涌上心来, "动态生成秒开的多Tab异形树的营销统计详情页". 这虽然是个前端的事, 但是要调的接口太多了, 干脆由后端用模板引擎渲染好了返回, 以往只要大胖提供接口就行了, 现在到好, 要调小十来个接口, 才能满足多Tab的要求, 这倒是好说, 多堆时间就可以了, 但是还要去处理麻烦的异形树结构, 这让上数据结构课就像听天书的大胖伤透了脑筋.

大胖不满的撅起嘴说道: "一切全都怪产品经理 Lisa 这个坏女人, 提的无理需求!"

俗话说的好, 只有懒程序员, 没有笨程序员, 大胖急中生智拿起电话打给了我,
我说: " 遇事不决, 量子力学, 我是 LeetCode 第一题都刷不过的人, 找我没用, 咱们找 Mason 大神, 一起开个线上会议吧".
大胖听完调侃道: "就这你还天天写技术文章吹牛呢? 这第一题我三个小时就解出来了,只是想讨论个最佳的实现方案, 才问问你滴, 不然就和你说话这功夫, 我代码都写完了".
虽然嘴上这么说, 行动却很诚实, 我被大胖匆忙邀请进了线上会议.
和 Mason 大神说完情况后, 他深沉的吟诵了一首定场诗.

南轩松 【朝代】 唐

南轩有孤松，柯叶自绵幂。

清风无闲时，潇洒终日夕。

阴生古苔绿，色染秋烟碧。

何当凌云霄，直上数千尺。

qrc4jiu1dcq.jpg-110.8kB

一对多树结构

对一般业务来说树形结构是在展示数据的适合需要, 而在增删改时则提前设计好一张或者多张表, 比如系统权限相关的用户表,角色表,权限表等, 这方面就不展开了, 最终通过业务主键的关联形成一颗抽象的树, 而这些树的结构大多是一个树枝(ParentNode)对应几个下级树枝(Node)在逐渐繁衍以此类推, 可能树枝下面挂着同一种果实(Object,List,Map), 但这与树的生长无关. 那么我们如何360°无死角的环视这颗树呢?

用抽象代码类比登录admin 时涉及的后台系统权限, 来一探究竟!

// pojo and enum

/**
* 一对多权限Node
*/
@Data
public class SoloNode {
   private Integer id ;
   private Integer permissionLevelEnum;
   private Integer parentId;
   private PermissionResource permissionResource;
   private List<SoloNode> children;

   public SoloNode(Integer id, Integer permissionLevelEnum, Integer parentId, PermissionResource permissionResource) {
       this.id = id;
       this.permissionLevelEnum = permissionLevelEnum;
       this.parentId = parentId;
       this.permissionResource = permissionResource;
   }
}

/**
* 权限相关的前端对应展示资源
*/
@Data
@AllArgsConstructor
public class PermissionResource {
   private String name;
   private String routePath;
   private String helpDescription;
   private String iconName;
   private String iconType;
}

/**
* 权限的层级关系Enum
*/
public enum PermissionLevelEnum implements  BasicEnum {
   PERMISSION_MENU(1, "权限菜单"),
   FINE_GRIT_PERMISSION(2, "细粒度权限");

   private Integer code;
   private String description;

   PermissionLevelEnum(final Integer code, final String description) {
       this.code = code;
       this.description = description;
   }

   @Override
   public Integer getCode() {
       return code;
   }

   @Override
   public String getDescription() {
       return description;
   }   
}

从这颗 SoloNode 树的属性可以看出来, 这是颗父子单层关联树. 因为没有预留多余的标记属性(如果要多层关联会比较麻烦). 那么我们来看看如何完全的展示出它吧 !

import studey.advance.datastructure.tree.SoloNode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by 刷题使我快乐,自律使我自由 !
 */
public class SoloTreeCompleteSolution {
    
    /**
     * 展示多颗完整的一对多 Tree
     * @param nodeList 构建树的子节点
     * @return TreeList
     */
    protected List<SoloNode> viewCompleteSoloTree(List<SoloNode> nodeList){
        List<SoloNode> soloTreeList = new ArrayList<>();
        for(SoloNode Node : getRootNode(nodeList)) {
            SoloNode nodex = buildChilTree(Node,nodeList);
            soloTreeList.add(nodex);
        }
        return soloTreeList;
    }
    
    /**
     * 为每个父节点递归 buildChilTree，建立子树形结构
     * @param pNode 需递归的父节点
     * @param nodeList 需递归的nodelist
     * @return 父节点Tree
     */
    private SoloNode buildChilTree(SoloNode pNode,List<SoloNode> nodeList){
        List<SoloNode> chils = new ArrayList<>();
        for(SoloNode Node : nodeList) {
            if(Node.getParentId().equals(pNode.getId())) {
                chils.add(buildChilTree(Node,chils));
            }
        }
        pNode.setChildren(chils);
        return pNode;
    }
    
    /**
     * 获取根节点 rootLists
     * @param nodeList 全部节点list
     * @return 根节点list
     */
    private List<SoloNode> getRootNode(List<SoloNode> nodeList) {
        List<SoloNode> rootLists = new  ArrayList<>();
        for(SoloNode node : nodeList) {
            if (node.getParentId().equals(-1)) {
                rootLists.add(node);
            }
        }
        return rootLists;
    }
}

测试用例如下

import org.junit.jupiter.api.Test;
import studey.advance.datastructure.enums.PermissionLevelEnum;
import studey.advance.datastructure.pojo.PermissionResource;
import studey.advance.datastructure.tree.SoloNode;
import studey.advance.datastructure.utils.JsonUtil;
import studey.advance.questiontypes.tree.SoloTreeCompleteSolution;

import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

  @Test
    void viewCompleteSoloTree() {
          List<SoloNode> soloList = new CopyOnWriteArrayList<>();
        soloList.add(new SoloNode(1, PermissionLevelEnum.PERMISSION_MENU.getCode(),-1,
            new PermissionResource("A网站运营菜单","/aWebsiteOperation","A网站运营帮助...","a-website-operation","svg")));
    
        soloList.add(new SoloNode(2, PermissionLevelEnum.PERMISSION_MENU.getCode(),1,
                new PermissionResource("A统计菜单","/statistics","统计帮助...","statistics","svg")));
        
        soloList.add(new SoloNode(3, PermissionLevelEnum.FINE_GRIT_PERMISSION.getCode(),2,
            new PermissionResource("A转换率统计权限","/conversionRate","转换率帮助...","conversion-rate","png")));
        soloList.add(new SoloNode(4, PermissionLevelEnum.FINE_GRIT_PERMISSION.getCode(),2,
            new PermissionResource("A曝光率统计权限","/exposureRate","曝光率帮助...","exposure-rate","png")));
        
        soloList.add(new SoloNode(5, PermissionLevelEnum.PERMISSION_MENU.getCode(),-1,
            new PermissionResource("资金总账管理菜单","/fundsManagement","资金总账帮助...","funds-management","svg")));
        soloList.add(new SoloNode(6, PermissionLevelEnum.FINE_GRIT_PERMISSION.getCode(),5,
            new PermissionResource("银行对账权限","/bankReconciliation","银行对账帮助...","bank-reconciliation","svg")));

        List<SoloNode> soloTree = this.viewCompleteSoloTree(soloList);
        System.out.println(JsonUtil.toJsonPretty(soloTree));
    }

json输出如下

[ {
  "id" : 1,
  "permissionLevelEnum" : 1,
  "parentId" : -1,
  "permissionResource" : {
    "name" : "A网站运营菜单",
    "routePath" : "/aWebsiteOperation",
    "helpDescription" : "A网站运营帮助...",
    "iconName" : "a-website-operation",
    "iconType" : "svg"
  },
  "children" : [ {
    "id" : 2,
    "permissionLevelEnum" : 1,
    "parentId" : 1,
    "permissionResource" : {
      "name" : "A统计菜单",
      "routePath" : "/statistics",
      "helpDescription" : "统计帮助...",
      "iconName" : "statistics",
      "iconType" : "svg"
    },
    "children" : [ ]
  } ]
}, {
  "id" : 5,
  "permissionLevelEnum" : 1,
  "parentId" : -1,
  "permissionResource" : {
    "name" : "资金总账管理菜单",
    "routePath" : "/fundsManagement",
    "helpDescription" : "资金总账帮助...",
    "iconName" : "funds-management",
    "iconType" : "svg"
  },
  "children" : [ {
    "id" : 6,
    "permissionLevelEnum" : 2,
    "parentId" : 5,
    "permissionResource" : {
      "name" : "银行对账权限",
      "routePath" : "/bankReconciliation",
      "helpDescription" : "银行对账帮助...",
      "iconName" : "bank-reconciliation",
      "iconType" : "svg"
    },
    "children" : [ ]
  } ]
} ]

可以看到 Json中 A统计菜单下并没有A转换率统计权与A曝光率统计权, 说明这种方式只能查看到父子结构的单层树, 如果父节点下面还有父节点在没有标记属性的情况下就比较难以察觉, 因此只适合部分单层树业务, 我们可以对树结构与算法进行升级来达到兼容的目的.

@Data
public class SoloNode {
    // 增加父节点标记属性
    private Boolean areParent;
      ...
    // 增加默认赋值
    private List<SoloNode> children = new ArrayList<>(1);
}

public class SoloTreeCompleteSolution {

 
      protected List<SoloNode> viewCompleteSoloTree(List<SoloNode> nodeList){
        List<SoloNode> soloTreeList = new ArrayList<>();
        for(SoloNode node : getRootNode(nodeList)) {
            List<Integer> ids = new ArrayList<>();
            this.buildParentIds(soloTreeList,ids);
            SoloNode nodex = buildChilTree(node,nodeList,ids);
            
            if (Boolean.FALSE.equals(ids.contains(nodex.getId()))){
                soloTreeList.add(nodex);
            }
        }
        return soloTreeList;
    }
  
     private List<SoloNode> getRootNode(List<SoloNode> nodeList) {
        List<SoloNode> rootLists = new  ArrayList<>();
        for(SoloNode node : nodeList) {
            if (Boolean.TRUE.equals(node.getAreParent())) {
                rootLists.add(node);
            }
        }
        return rootLists;
    }
  
      private void buildParentIds(List<SoloNode> nodeList, List<Integer> ids ){
        for(SoloNode node : nodeList) {
            if (Boolean.TRUE.equals(node.getAreParent())) {
                ids.add(node.getId());
                this.buildParentIds(node.getChildren(),ids);
            }
        }
    }
}

最终输出

[ {
  "id" : 1,
  "permissionLevelEnum" : 1,
  "parentId" : -1,
  "areParent" : true,
  "permissionResource" : {
    "name" : "A网站运营菜单",
    "routePath" : "/aWebsiteOperation",
    "helpDescription" : "A网站运营帮助...",
    "iconName" : "a-website-operation",
    "iconType" : "svg"
  },
  "children" : [ {
    "id" : 2,
    "permissionLevelEnum" : 1,
    "parentId" : 1,
    "areParent" : true,
    "permissionResource" : {
      "name" : "A统计菜单",
      "routePath" : "/statistics",
      "helpDescription" : "统计帮助...",
      "iconName" : "statistics",
      "iconType" : "svg"
    },
    "children" : [ {
      "id" : 3,
      "permissionLevelEnum" : 2,
      "parentId" : 2,
      "areParent" : false,
      "permissionResource" : {
        "name" : "A转换率统计权限",
        "routePath" : "/conversionRate",
        "helpDescription" : "转换率帮助...",
        "iconName" : "conversion-rate",
        "iconType" : "png"
      },
      "children" : [ ]
    }, {
      "id" : 4,
      "permissionLevelEnum" : 2,
      "parentId" : 2,
      "areParent" : false,
      "permissionResource" : {
        "name" : "A曝光率统计权限",
        "routePath" : "/exposureRate",
        "helpDescription" : "曝光率帮助...",
        "iconName" : "exposure-rate",
        "iconType" : "png"
      },
      "children" : [ ]
    } ]
  } ]
}, {
  "id" : 5,
  "permissionLevelEnum" : 1,
  "parentId" : -1,
  "areParent" : true,
  "permissionResource" : {
    "name" : "资金总账管理菜单",
    "routePath" : "/fundsManagement",
    "helpDescription" : "资金总账帮助...",
    "iconName" : "funds-management",
    "iconType" : "svg"
  },
  "children" : [ {
    "id" : 6,
    "permissionLevelEnum" : 2,
    "parentId" : 5,
    "areParent" : false,
    "permissionResource" : {
      "name" : "银行对账权限",
      "routePath" : "/bankReconciliation",
      "helpDescription" : "银行对账帮助...",
      "iconName" : "bank-reconciliation",
      "iconType" : "svg"
    },
    "children" : [ ]
  } ]
} ]

通过标记父节点与build时剔除被构建过的子树, 这样多层的一对多树结构就完整的展示出来了, 但是这种实现方式比较蹩脚, 会进行一些无效计算, 影响性能, 下个例子会给出优化方法, 欢迎提 PR来优化.

https://github.com/XiaoZiShan/studey-advance/blob/e52a88fea306b066b2cc70335fb797d2468c791a/src/test/java/advance/datastructure/tree/SoloCompleteSolutionTest.java

12

多对多异形结构

在上个例子中可以看到我们用了递归来遍历树, 而中很多计算都是重复的，由于其本质是把一个问题分解成两个或者多个小问题，多个小问题存在相互重叠的部分，则存在重复计算，如用于生产则会因树的层级增多以及树的品种变多, 导致算法复杂度由 O(n) 变成 O(n!), 最终严重影响展示速度. 而在这个场景里递归只是为了感知子节点, 如果我们提前让子节点知道它有那些父节点, 情况会好很多. 那么下面来看看多对多的异形树应该如何环视吧 !

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.EqualsAndHashCode;
import studey.advance.datastructure.pojo.PermissionResource;

import java.util.ArrayList;
import java.util.List;

/**
* Created by 刷题使我快乐,自律使我自由 !
* 多对多用户-角色-权限树
*/
@Data
@AllArgsConstructor
public class MultNode {
  private Integer id;
  private String userName;
  private List<RoleNode> roleNodes = new ArrayList<>();


  @Data
  public static class RoleNode{
      private Integer id;
      private String name;
      private List<Integer> parentIds;
      private Boolean areParent;
      private List<PermissionNode> permissions = new ArrayList<>();
      private List<RoleNode> children = new ArrayList<>();;

      public RoleNode(Integer id, String name, List<Integer> parentIds, Boolean areParent, List<PermissionNode> permissions) {
          this.id = id;
          this.name = name;
          this.parentIds = parentIds;
          this.areParent = areParent;
          this.permissions = permissions;
      }
  }

  @Data
  @EqualsAndHashCode(callSuper = true)
  public static class PermissionNode extends SoloNode{
      private List<Integer> parentIds;

      public PermissionNode(List<Integer> parentIds, Integer id, Integer permissionLevelEnum, Integer parentId, Boolean areParent, PermissionResource permissionResource) {
          super(id, permissionLevelEnum, parentId, areParent, permissionResource);
          this.setParentIds(parentIds);
      }
  }

}

在环视时继承原先的单树算法. 比较两者的区别.

import studey.advance.datastructure.tree.MultNode;
import studey.advance.datastructure.tree.SoloNode;
import java.util.List;

public class MultTreeCompleteSolution extends SoloTreeCompleteSolution{

    /**
     * 当前仅供演示用的新BuildTree思路, 代码严谨性后续完善
     * @param multNodes 未关联的多对多树
     * @param roleNodes 角色树
     * @param permissionNodes 权限树
     * @return 已关联的多对多树
     */
    protected List<MultNode> viewCompleteMultTree(List<MultNode> multNodes, List<MultNode.RoleNode> roleNodes , List<SoloNode> permissionNodes) {
        for (MultNode nodeX : multNodes) {

            // 遍历角色Tree (查询nodeX的角色节点并拼接组装)
            for (MultNode.RoleNode roleX : nodeX.getRoleNodes()) {
                for (MultNode.RoleNode roleY : roleNodes) {
                    if (roleY.getParentIds().contains(roleX.getId())) {
                        roleX.getChildren().add(roleY);
                        break;
                    }
                }

                // 用老的迭代树方式来递归权限树, 进行比较
                for (MultNode.PermissionNode permissionX : roleX.getPermissions()){
                    List<SoloNode> soloNodes = this.viewCompleteSoloTree(permissionNodes);
                    for (SoloNode soloNodeY: soloNodes){
                        if (permissionX.getId().equals(soloNodeY.getId())){
                            permissionX.setChildren(soloNodeY.getChildren());
                        }
                    }
                }
            }
        }
        return multNodes;
    }

}

单元测试数据在原先的基础上增加

import org.junit.jupiter.api.Test;
import studey.advance.datastructure.enums.PermissionLevelEnum;
import studey.advance.datastructure.pojo.PermissionResource;
import studey.advance.datastructure.tree.MultNode;
import studey.advance.datastructure.tree.SoloNode;
import studey.advance.datastructure.utils.JsonUtil;
import studey.advance.questiontypes.tree.MultTreeCompleteSolution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class MultCompleteSolutionTest extends MultTreeCompleteSolution {

    @Test
    void viewCompleteSoloTree() {


        List<SoloNode> permissionNodes = new ArrayList<>();
        MultNode.PermissionNode aWwwOperation = new MultNode.PermissionNode(Collections.singletonList(-1),1, PermissionLevelEnum.PERMISSION_MENU.getCode(),-1,Boolean.TRUE,
            new PermissionResource("A网站运营菜单","/aWebsiteOperation","A网站运营帮助...","a-website-operation","svg"));
        permissionNodes.add(aWwwOperation);
        permissionNodes.add(new MultNode.PermissionNode(Collections.unmodifiableList(Arrays.asList(-1,1)),2, PermissionLevelEnum.PERMISSION_MENU.getCode(),1,Boolean.TRUE,
            new PermissionResource("A统计菜单","/statistics","统计帮助...","statistics","svg")));

        permissionNodes.add(new MultNode.PermissionNode(Collections.unmodifiableList(Arrays.asList(-1,1,2)),3, PermissionLevelEnum.FINE_GRIT_PERMISSION.getCode(),2,Boolean.FALSE,
            new PermissionResource("A转换率统计权限","/conversionRate","转换率帮助...","conversion-rate","png")));
        permissionNodes.add(new MultNode.PermissionNode(Collections.unmodifiableList(Arrays.asList(-1,1,2)),4, PermissionLevelEnum.FINE_GRIT_PERMISSION.getCode(),2, Boolean.FALSE,
            new PermissionResource("A曝光率统计权限","/exposureRate","曝光率帮助...","exposure-rate","png")));

        MultNode.PermissionNode moneyGeneralLedger = new MultNode.PermissionNode(Collections.singletonList(-1),5, PermissionLevelEnum.PERMISSION_MENU.getCode(),-1,Boolean.TRUE,
            new PermissionResource("资金总账管理菜单","/fundsManagement","资金总账帮助...","funds-management","svg"));

        permissionNodes.add(moneyGeneralLedger);
        permissionNodes.add(new MultNode.PermissionNode(Collections.unmodifiableList(Arrays.asList(-1,5)),6, PermissionLevelEnum.FINE_GRIT_PERMISSION.getCode(),5,Boolean.FALSE,
            new PermissionResource("银行对账权限","/bankReconciliation","银行对账帮助...","bank-reconciliation","svg")));

        List<MultNode.RoleNode> roleNodes = new ArrayList<>();
        MultNode.RoleNode directorNetworkOperations = new MultNode.RoleNode(1,"全网运营总监", Collections.singletonList(-1),Boolean.TRUE, new ArrayList<>());
        roleNodes.add(directorNetworkOperations);
        MultNode.RoleNode roleNodex = new MultNode.RoleNode(2,"A网运营总监", Collections.singletonList(1),Boolean.TRUE, new ArrayList<>(Collections.singletonList(aWwwOperation)));
        roleNodes.add(roleNodex);

        MultNode.RoleNode chiefAccountantGeneraLedger = new MultNode.RoleNode(3,"总账首席会计师", Collections.singletonList(-1),Boolean.TRUE, new ArrayList<>(Collections.singletonList(moneyGeneralLedger)));
        roleNodes.add(chiefAccountantGeneraLedger);

        List<MultNode> multNodes = new ArrayList<>();
        multNodes.add(new MultNode(1,"运营老李",Collections.singletonList(directorNetworkOperations)));
        multNodes.add(new MultNode(1,"会计老张",Collections.singletonList(chiefAccountantGeneraLedger)));

        List<MultNode> multTree = this.viewCompleteMultTree(multNodes,roleNodes,permissionNodes);
        System.out.println(JsonUtil.toJsonPretty(multTree));
    }
}

最终输出, 欢迎提PR优化

[[ {
  "id" : 1,
  "userName" : "运营老李",
  "roleNodes" : [ {
    "id" : 1,
    "name" : "全网运营总监",
    "parentIds" : [ -1 ],
    "areParent" : true,
    "permissions" : [ ],
    "children" : [ {
      "id" : 2,
      "name" : "A网运营总监",
      "parentIds" : [ 1 ],
      "areParent" : true,
      "permissions" : [ {
        "id" : 1,
        "permissionLevelEnum" : 1,
        "parentId" : -1,
        "areParent" : true,
        "permissionResource" : {
          "name" : "A网站运营菜单",
          "routePath" : "/aWebsiteOperation",
          "helpDescription" : "A网站运营帮助...",
          "iconName" : "a-website-operation",
          "iconType" : "svg"
        },
        "children" : [ {
          "id" : 2,
          "permissionLevelEnum" : 1,
          "parentId" : 1,
          "areParent" : true,
          "permissionResource" : {
            "name" : "A统计菜单",
            "routePath" : "/statistics",
            "helpDescription" : "统计帮助...",
            "iconName" : "statistics",
            "iconType" : "svg"
          },
          "children" : [ {
            "id" : 3,
            "permissionLevelEnum" : 2,
            "parentId" : 2,
            "areParent" : false,
            "permissionResource" : {
              "name" : "A转换率统计权限",
              "routePath" : "/conversionRate",
              "helpDescription" : "转换率帮助...",
              "iconName" : "conversion-rate",
              "iconType" : "png"
            },
            "children" : [ ],
            "parentIds" : [ -1, 1, 2 ]
          }, {
            "id" : 4,
            "permissionLevelEnum" : 2,
            "parentId" : 2,
            "areParent" : false,
            "permissionResource" : {
              "name" : "A曝光率统计权限",
              "routePath" : "/exposureRate",
              "helpDescription" : "曝光率帮助...",
              "iconName" : "exposure-rate",
              "iconType" : "png"
            },
            "children" : [ ],
            "parentIds" : [ -1, 1, 2 ]
          } ],
          "parentIds" : [ -1, 1 ]
        } ],
        "parentIds" : [ -1 ]
      } ],
      "children" : [ ]
    } ]
  } ]
}, {
  "id" : 1,
  "userName" : "会计老张",
  "roleNodes" : [ {
    "id" : 3,
    "name" : "总账首席会计师",
    "parentIds" : [ -1 ],
    "areParent" : true,
    "permissions" : [ {
      "id" : 5,
      "permissionLevelEnum" : 1,
      "parentId" : -1,
      "areParent" : true,
      "permissionResource" : {
        "name" : "资金总账管理菜单",
        "routePath" : "/fundsManagement",
        "helpDescription" : "资金总账帮助...",
        "iconName" : "funds-management",
        "iconType" : "svg"
      },
      "children" : [ {
        "id" : 6,
        "permissionLevelEnum" : 2,
        "parentId" : 5,
        "areParent" : false,
        "permissionResource" : {
          "name" : "银行对账权限",
          "routePath" : "/bankReconciliation",
          "helpDescription" : "银行对账帮助...",
          "iconName" : "bank-reconciliation",
          "iconType" : "svg"
        },
        "children" : [ ],
        "parentIds" : [ -1, 5 ]
      } ],
      "parentIds" : [ -1 ]
    } ],
    "children" : [ ]
  } ]
} ]

https://github.com/XiaoZiShan/studey-advance/blob/master/src/test/java/advance/datastructure/tree/MultCompleteSolutionTest.java

image.png

简洁回答以及总结

可以看到用维护父ids的方式可以替代部分递归树的场景, 提高运行效率. 以上代码只是demo, 还有很多边界问题以及可以优化的点, 比如用 减少无效计算, 用一个Map来代替一部分遍历工作, 抽象一个专门处理树形结构的工具类等等.

总之本文对一般的树形场景都涉及到了, 公司做业务的时候可以提前定义树形结构的写法, 开发新业务时只需要继承抽象对象然后调工具类即可. 这树形结构本身不复杂, 它不是我们常见的树结构. 比如红黑树, AVL树等, 而是一种为了展示而生拼装成的数据结构.

Tip

Mason 大神云淡风轻的说道: "大胖要加强基本功啊, 这个树只是非常简单的一种展示结构, 要是让你开发一款类似MySql的索引, 那你不是得上吊啊, 基础就像内裤, 平时不知道穿没穿, 关键的时候就容易掉链子 ! "

大胖红着脸说道: "这就去把王者农药卸载, 每天早睡早起, 以后咱们B站学习区见, 爷青回!"

我一声长叹道: "早知现在, 何必当初!"

山中问答 【朝代】 唐

问余何意栖碧山，笑而不答心自闲。

桃花流水窅然去，别有天地非人间。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,362评论 5赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,330评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,247评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,560评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,580评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,569评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,929评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,587评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,840评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,596评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,678评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,366评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,945评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,929评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,165评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 43,271评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,403评论 2赞 342

推荐阅读更多精彩内容