Java ArrayDeque实现通用树DFS与BFS遍历顺序异常问题

用Java的ArrayDeque实现通用树的DFS和BFS遍历，在特定树形下两种遍历返回相同节点顺序，不符合预期。

测试树形结构 #

root
       /    \
   child1  child2
     |        |
 grandchild1  grandchild2

节点类实现 #

节点仅存储parentId，不直接持有子节点：

public class Node {
    private UUID id;
    private String value;
    private UUID parentId;   // null if root
    private UUID treeId;
}

DFS实现（ArrayDeque作为栈） #

public List<Node> dfs(List<Node> nodes) {
    Node root = nodes.stream()
            .filter(n -> n.getParentId() == null)
            .findFirst()
            .orElseThrow();

    ArrayDeque<UUID> stack = new ArrayDeque<>();
    stack.push(root.getId());
    List<Node> result = new ArrayList<>();

    Map<UUID, Node> nodeMap = nodes.stream()
            .collect(Collectors.toMap(Node::getId, n -> n));

    while (!stack.isEmpty()) {
        UUID currentId = stack.pop();
        Node current = nodeMap.get(currentId);
        result.add(current);

        List<Node> children = nodes.stream()
                .filter(n -> currentId.equals(n.getParentId()))
                .collect(Collectors.toList());

        children.forEach(child -> stack.push(child.getId()));
    }
    return result;
}

BFS实现（ArrayDeque作为队列） #

public List<Node> bfs(List<Node> nodes) {
    Node root = nodes.stream()
            .filter(n -> n.getParentId() == null)
            .findFirst()
            .orElseThrow();

    ArrayDeque<UUID> queue = new ArrayDeque<>();
    queue.add(root.getId());
    List<Node> result = new ArrayList<>();

    Map<UUID, Node> nodeMap = nodes.stream()
            .collect(Collectors.toMap(Node::getId, n -> n));

    while (!queue.isEmpty()) {
        UUID currentId = queue.poll();
        Node current = nodeMap.get(currentId);
        result.add(current);

        List<Node> children = nodes.stream()
                .filter(n -> currentId.equals(n.getParentId()))
                .collect(Collectors.toList());

        children.forEach(child -> queue.add(child.getId()));
    }
    return result;
}

观察到的行为与预期 #

• 实际结果：两种遍历均返回顺序：root → child1 → grandchild1 → child2 → grandchild2
• 预期结果：
  • DFS：root → child1 → grandchild1 → child2 → grandchild2（符合预期）
  • BFS：root → child1 → child2 → grandchild1 → grandchild2（不符合预期）

关键疑问 #

与常规树形实现（节点持有List<Node> children）不同，本实现中节点仅存储parentId，子节点通过运行时过滤全节点列表获取，这是否会影响遍历顺序？

已尝试操作 #

• 确认ArrayDeque的push/pop为LIFO、add/poll为FIFO，逻辑正确
• 测试线性树（每个节点仅一个子节点），两者结果一致，符合预期
• 仅当节点有2个及以上同级子节点时，差异才会显现

解答 #

核心原因 #

你的BFS结果不符合预期，大概率是测试数据的树形结构与描述不符，或子节点过滤逻辑存在遗漏：

1. 若实际测试数据中child2的parentId是child1的ID而非root的ID，树形结构会变成线性链（root→child1→grandchild1→child2→grandchild2），此时DFS和BFS的遍历顺序自然一致。
2. 若存在多棵树的节点混合在nodes列表中，未通过treeId过滤同一棵树的节点，可能导致子节点获取错误，破坏BFS的层级遍历逻辑。

验证与修复步骤 #

1. 校验测试数据：确认child2的parentId确实指向root的ID，符合描述的树形结构。
2. 完善子节点过滤逻辑：若存在多棵树，需增加treeId匹配，避免跨树获取子节点：

   List<Node> children = nodes.stream()
           .filter(n -> currentId.equals(n.getParentId()) && current.getTreeId().equals(n.getTreeId()))
           .collect(Collectors.toList());
   

3. 固定子节点遍历顺序：若需要稳定的子节点顺序（如按value排序），可在过滤后对列表排序，避免依赖原始nodes列表的插入顺序：

   List<Node> children = nodes.stream()
           .filter(n -> currentId.equals(n.getParentId()) && current.getTreeId().equals(n.getTreeId()))
           .sorted(Comparator.comparing(Node::getValue))
           .collect(Collectors.toList());
   

关于遍历顺序的疑问 #

子节点通过过滤全节点列表获取的方式，只会影响子节点的先后顺序（比如child1和child2的遍历先后），但不会导致BFS变成DFS的遍历逻辑——只要过滤逻辑正确，BFS依然会遵循层级遍历的规则。

内容的提问来源于stack exchange，提问作者Héctor Mellado