如何实现递归函数为Item列表生成parentIds字段

需求说明 #

• 为每个Item添加List<String> parentIds字段，存储其所有最终父节点ID（即没有父节点的顶层节点）
• 递归函数要求：
  • 接收List<String>类型的ids参数，返回List<String>类型的最终父节点ID列表
  • 基准条件：若当前ID没有父节点（无元素的childIds包含该ID），则保留该ID并终止递归
  • 递归逻辑：对当前ID的父节点ID继续递归查找，直到找到无父节点的顶层节点

原始数据 #

List<Item> data = [
  Item(id: 'aaa', childIds: ['ccc']),
  Item(id: 'bbb', childIds: ['ccc', 'ddd']),
  Item(id: 'ccc', childIds: ['ggg']),
  Item(id: 'ddd', childIds: ['fff','hhh']),
  Item(id: 'eee', childIds: ['hhh']),
  Item(id: 'fff', childIds: ['ggg']),
  Item(id: 'ggg', childIds: null),
  Item(id: 'hhh', childIds: null),
];

期望结果 #

List<Item> data = [
  Item(id: 'aaa', childIds: ['ccc'], parentIds: []),
  Item(id: 'bbb', childIds: ['ccc', 'ddd'], parentIds: []),
  Item(id: 'ccc', childIds: ['ggg'], parentIds: ['aaa','bbb']),
  Item(id: 'ddd', childIds: ['fff','hhh'], parentIds: ['bbb']),
  Item(id: 'eee', childIds: ['hhh'], parentIds: []),
  Item(id: 'fff', childIds: ['ggg'], parentIds: ['bbb']),
  Item(id: 'ggg', childIds: null, parentIds: ['aaa','bbb']),
  Item(id: 'hhh', childIds: null, parentIds: ['bbb','eee']),
];

修改后的完整代码 #

替换原有的findParent1和findParent2为单个递归函数findFinalParents，实现逻辑如下：

• 先获取当前所有ID的直接父节点ID集合
• 如果没有父节点，直接返回当前ID集合（基准条件）
• 如果有父节点，递归调用自身查找这些父节点的最终父节点

class Item {
  Item({this.id, this.childIds, this.parentIds});

  final String id;
  final List<String> childIds;
  List<String> parentIds;

  @override
  String toString() {
    return 'Item{id: $id, childIds: $childIds, parentIds: $parentIds}';
  }
}

List<Item> data = [
  Item(id: 'aaa', childIds: ['ccc']),
  Item(id: 'bbb', childIds: ['ccc', 'ddd']),
  Item(id: 'ccc', childIds: ['ggg']),
  Item(id: 'ddd', childIds: ['fff','hhh']),
  Item(id: 'eee', childIds: ['hhh']),
  Item(id: 'fff', childIds: ['ggg']),
  Item(id: 'ggg', childIds: null),
  Item(id: 'hhh', childIds: null),
];

void main() {
  data.forEach((e) => e.parentIds = idFindParent(e.id));
  data.forEach((e) => print(e));
}

List<String> idFindParent(String id) {
  // 获取当前ID的直接父节点ID
  List<String> directParentIds = data
      .where((item) => item.childIds != null && item.childIds.contains(id))
      .map((item) => item.id)
      .toSet()
      .toList();
  
  // 递归查找最终父节点
  return findFinalParents(directParentIds);
}

// 递归函数：查找给定ID列表的最终父节点
List<String> findFinalParents(List<String> ids) {
  // 去重避免重复处理
  Set<String> uniqueIds = ids.toSet();
  if (uniqueIds.isEmpty) {
    return [];
  }

  // 收集所有当前ID的直接父节点
  Set<String> parentIds = {};
  for (String id in uniqueIds) {
    var parents = data.where((item) => 
      item.childIds != null && item.childIds.contains(id)
    ).map((item) => item.id);
    parentIds.addAll(parents);
  }

  // 基准条件：没有父节点，返回当前ID集合
  if (parentIds.isEmpty) {
    return uniqueIds.toList();
  }

  // 递归：查找父节点的最终父节点
  return findFinalParents(parentIds.toList());
}

代码说明 #

1. idFindParent函数：先获取目标ID的直接父节点，再调用递归函数查找最终父节点
2. findFinalParents递归函数：
   • 第一步对输入ID去重，避免重复计算
   • 收集所有当前ID的直接父节点
   • 如果没有父节点，直接返回当前ID（顶层节点）
   • 如果有父节点，递归调用自身，继续查找这些父节点的最终父节点
3. 全程使用Set去重，保证parentIds中没有重复的节点ID

内容的提问来源于stack exchange，提问作者Kel