recursion - Treesort dart - 根据父/子重新排序列表

Question

我有一个问题：我有一个这样的列表：

List flat = [
  { id: 1, parentId: 3 },
  { id: 3, parentId: 8 },
  { id: 4, parentId: 6 },
  { id: 6, parentId: 3 },
  { id: 7, parentId: 6 },
  { id: 8, parentId: null },
  { id: 10, parentId: 8 }, 
  { id: 13, parentId: 14 },
  { id: 14, parentId: 10 }
]

我想动态地将此列表构造为以下内容：

[
  { 
    id: 8,
    children: [
      { 
        id: 3, 
        children: [
          { 
            id: 1, 
            children: [] 
          }, 
          { 
            id: 6, 
            children: [ 
              { id: 4, children: [] }, 
              { id: 7, children: [] } 
            ]
          }
        ] 
      },
      { 
        id: 10, 
        children: [ 
          { 
            id: 14, 
            children: [
              { id: 13, children: [] }
            ] 
          }
        ]
      }
    ]
  }
]

我用 javascript 找到了多个示例，但是我怎样才能用 dart 来实现呢？

标签： recursiondarttree

Answer 1

怎么样：

 /// Tree-order nodes by their "parentId".
 ///
 /// Returns the root. Assumes there is exactly one root.
 Map<String, dynamic> treeOrder(List<Map<String, dynamic>> nodes) {
  // Each node has a key and a parent. 
  // Change them all to have no parent and a children list.
  var map = <int, Map<String, dynamic>>{};
  for (var node in nodes) {
    map[node["id"]] = node;
    node["children"] = [];
  }
  Map<String, dynamic> result;
  for (var node in nodes) {
    var parentId = node.remove("parentId");
    if (parentId == null) {
      result = node;
    } else {
      map[parentId]["children"].add(node);
    }
  }
  return result;
}

没有什么特别聪明的，只是保持从 id 到 value 的映射以加快查找速度。