求遍历树形结构的全部子节点

Question

从数据库查询出了部门表的全部列表，已经遍历组装成了树形结构，如何获取每个部门的全部子节点(包括子孙节点)，也就是下面这种结构：
List<{deptId=1,nextId=2}>
List<{deptId=1,nextId=3}>
List<{deptId=1,nextId=4}>
List<{deptId=1,nextId=5}>
List<{deptId=1,nextId=6}>
List<{deptId=1,nextId=7}>
List<{deptId=1,nextId=8}>
List<{deptId=2,nextId=5}>
List<{deptId=2,nextId=6}>
List<{deptId=5,nextId=7}>
List<{deptId=5,nextId=8}>

求大佬给个算法点拨，谢谢

14点22补充
treeList是已经转换了的树形List

DeptLevel类是最终存储部门层级的对象

结果需要是：
XX科技---技术部
XX科技---开发部
XX科技---前端组
XX科技---JAVA组
XX科技---测试部
XX科技---财务部
技术部---开发部
技术部---前端组
技术部---JAVA组
。。。

Answer 1

我不知道你树形结构是啥样的，我这里用DeptTree做树形结构，你的那个{deptId,nextId}结构的数据，我用Dept对应。

我也不确定你对遍历的顺序是否有要求，按照深度优先算法写了个。

public class Sample {

    public static void main(String[] args) {

        DeptTree root = new DeptTree(1);
        DeptTree root2 = new DeptTree(2);
        DeptTree root5 = new DeptTree(5);

        root.addChild(root2);
        root.addChild(new DeptTree(3));
        root.addChild(new DeptTree(4));

        root2.addChild(root5);
        root2.addChild(new DeptTree(6));

        root5.addChild(new DeptTree(7));
        root5.addChild(new DeptTree(8));

        List<Dept> result = new LinkedList<>();

        traverse(root, result);
        System.out.println(result);
    }

    /**
     *  深度优先遍历 遍历树形list
     */
    public static void traverse(DeptTree curTree, List<Dept> result) {
        List<DeptTree> children = curTree.children;

        convert(curTree, children, result);

        for (DeptTree child : children) {
            traverse(child, result);
        }

    }

    /**
     * 深度优先遍历 以curTree为根节点，获取所有子孙节点
     */
    public static void convert(DeptTree curTree, List<DeptTree> children, List<Dept> result) {
        int deptId = curTree.deptId;

        if (children.size() == 0) { //没有子节点了
            return;
        }

        for (DeptTree child : children) {
            result.add(new Dept(deptId, child.deptId));
            convert(curTree, child.children, result);
        }
    }
}


class DeptTree {

    public DeptTree(int deptId) {
        this.deptId = deptId;
    }

    public int deptId;
    public List<DeptTree> children = new LinkedList<DeptTree>();

    public void addChild(DeptTree child) {
        children.add(child);
    }

}

class Dept {

    public Dept(int deptId, int nextId) {
        this.deptId = deptId;
        this.nextId = nextId;
    }

    public int deptId;
    public int nextId;
}

Answer 2

Java 递归实例操作-查询层级菜单
https://ichochy.com/posts/20210315.html

Answer 3

参考以下方法

// 树形结构
@Builder
@AllArgsConstructor
@NoArgsConstructor
@Data
public class MultiTree {

    /**
     * id
     */
    private Integer id;
    /**
     * 父id
     */
    private Integer pid;
    /**
     * 名称
     */
    private String name;
    /**
     * 子列表
     */
    private List<MultiTree> childrenList = CollUtil.newArrayList();

}

// 平面结构
@Builder
@AllArgsConstructor
@NoArgsConstructor
@Data
public class SingleTree {

    /**
     * id
     */
    private Integer id;
    /**
     * 父id
     */
    private Integer pid;
    /**
     * 名称
     */
    private String name;

}

// 转换类
public class TreeConvert {

    /**
     * 转换成平面结构树
     */
    private static List<SingleTree> convertToSingleTree(List<MultiTree> multiTreeList) {
        List<SingleTree> singleTreeList = CollUtil.newArrayList();
        // 找出所有父节点
        for (MultiTree multiTree : multiTreeList) {
            singleTreeList.add(
                SingleTree.builder().id(multiTree.getId()).pid(multiTree.getPid()).name(multiTree.getName()).build());
        }
        // 找出所有子节点
        for (MultiTree multiTree : multiTreeList) {
            convertToSingleTreeChildren(singleTreeList, multiTree);
        }
        return singleTreeList;
    }

    /**
     * 转换成平面结构树的子节点
     */
    private static void convertToSingleTreeChildren(List<SingleTree> singleTreeList, MultiTree multiTree) {
        for (int i = 0; i < singleTreeList.size(); i++) {
            SingleTree singleTree = singleTreeList.get(i);
            int id = multiTree.getId();
            if (Objects.equals(singleTree.getId(), id)) {
                List<MultiTree> childrenList = multiTree.getChildrenList();
                if (CollUtil.isNotEmpty(childrenList)) {
                    for (MultiTree children : childrenList) {
                        singleTreeList
                            .add(SingleTree.builder().id(children.getId()).pid(id).name(children.getName()).build());
                        convertToSingleTreeChildren(singleTreeList, children);
                    }
                }
            }
        }
    }

}