关于电商平台如何遍历所有下级的实现

背景

电商平台邀请人和被邀请人是有层级关系的，比如A邀请B，B邀请C，C邀请D，C又邀请了E。那么A的下级就是B、C、D、E
在很多场景下，邀请人都可以通过下级获取利益，分红。那么我们该如何获取A的所有下级呢？

实现

如果我们是用一个人去找他的所有的上级。那我们可以直接递归实现。比如先获取这个用户的邀请人，再不断地向上寻找，直到找到没有上级的那个邀请人（根）为止。

但是如果是一个人去寻找他的所有下级。那大概率就是一个树形结构。而且是无限层级的树。我们如果用递归的话会对性能造成很大的消耗，并且极有可能造成栈溢出。

我们可以换一种办法。

用人口普查的例子来说。就是一个登记员先拿走这个人的名字，并登陆他的信息，然后问这个人：你的儿子**（直接下级）是谁？
然后把闻出来的所有的儿子的名字都记录下来（假设B、C），依次写在待等级名单的末尾。
登记员再从名单的最前面打走下个名字（B），然后继续问：你的儿子（直接下级）**是谁？然后把B的直接下级（D、E）写在名单末尾。
就这样以此类推，直到名单空为止。

好处

好处在于我们是使用队列实现该功能，而队列存储在堆内存中，空间很大，更不用担心栈溢出。
而且我们是一层层的登记，使用的广度优先搜索
从头到尾只有一个主循环在工作，没有层层递归，也不需要嵌套函数
队列大小相对来说可控，而且队列大小主要取决于树的宽度，一个人也不太可能邀请成千上万个人。

实现（java伪代码）

import java.util.*;
import java.util.stream.Collectors;

public List<User> findAllSubordinatesStream(Long rootUserId) {
    // 0. 准备结果集和已访问集合 (防环)
    List<User> allSubordinates = new ArrayList<>();
    Set<Long> visited = new HashSet<>();

    // 1. 创建队列 (ArrayDeque在这个场景下要强于LinkedList，详见下文)
    Queue<Long> userIdQueue = new ArrayDeque<>();

    // 2. 初始化：根节点入队并标记访问
    userIdQueue.offer(rootUserId);
    visited.add(rootUserId);

    // 3. 主循环
    while (!userIdQueue.isEmpty()) {
        // 3.1 出队当前用户ID
        Long currentUserId = userIdQueue.poll();

        // 3.2 查询当前用户的直接下级 (findDirectSubordinates这个方法返回List<User>，里面承载该用户所有直接下级)
        List<User> directSubs = userService.findDirectSubordinates(currentUserId);

        // 3.3 使用Stream处理直接下级列表 (核心优化)
        directSubs.stream()
                // 过滤掉已经访问过的下级 (防环)
                .filter(sub -> !visited.contains(sub.getId()))
                // 对每个未访问的下级执行操作 (forEach是终端操作)
                .forEach(sub -> {
                    // 获取下级ID
                    Long subId = sub.getId();
                    // 标记为已访问 (必须放在加入队列前，防止其他路径重复添加)
                    visited.add(subId);
                    // 将该下级ID加入队列 (等待后续处理其下级)
                    userIdQueue.offer(subId);
                    // 将该下级用户对象加入最终结果集
                    allSubordinates.add(sub);
                });
    }

    // 4. 返回所有下级用户
    return allSubordinates;
}

关于队列的拓展知识

性质

首先队列是一个先进先出的数据结构
在Java中的Queue队列的api主要有：

  1. 添加元素（入队）
    boolean offer(E e)
    将元素e插入队列尾部

  2. 移除并返回元素（出队）
    E poll()
    将头部元素移除并返回

  3. 查看头部元素（不移除）
    E peek()
    尝试获取但不移除队列头部的元素

以上这一组操作都是安全的操作 不会抛异常
下面是会抛异常的对应的api，不建议使用

add remove element

实现类

  1. LinkedList：理论上无界，只受内存限制
  2. ArrayDeque：构造时可以指定初始容量（默认16），自动扩容

这两个类都不是线程安全的。

为什么用ArrayDeque而不是LinkedList？

打个比方。ArrayDeque相当于候车厅里面的一排排固定连接在一起的座椅。
优点自然就是座位紧凑（内容连续）。CPU一眼就能看到头尾，出入队非常高效，
缺点就是作为总数优先，人太多时需要不断扩容，而且不支持在中间加入/删除

LinkedList就像车站广场上分散的乘客，每个人都知道自己的前后是谁。
优点是可以无线接纳乘客，在队伍任何位置插入或者拉走人相对容易。
缺点就是内存不连续，CPU需要进行指针跳转，效率第，占用更多空间

关于栈的拓展知识

性质

栈就是一个先进后出的数据结构了。就像一个有底没盖的容器。

  1. 入栈
    void push(E e)

  2. 出栈
    E pop()

  3. 查看栈顶元素
    E peek()

  4. 查看栈是否为空
    boolean isEmpty()