Scala - 展平树结构

Question

我有一个从 Java 库接收的树结构。我试图将它展平，因为我只对树的“关键”值感兴趣。该树由以下零个或多个类组成:

class R(val key: String, val nodes: java.util.List[R]) {}

用一个空节点列表表示分支的结束。可以通过以下代码构建示例:

val sample =  List[R](
  new R("1",  List[R](
    new R("2",  List[R]().asJava),
    new R("3",  List[R](new R("4",  List[R]().asJava))
      .asJava)).asJava)).asJava

我在编写正确的方法和有效的方法时遇到了麻烦。这是我到目前为止:

def flattenTree(tree: List[R]): List[String] = {
  tree.foldLeft(List[String]())((acc, x) => 
             x.key :: flattenTree(x.nodes.asScala.toList))
}

然而，当我运行这段代码时，尽管它可能效率低下，但我仍然认为它不正确。我的结果最终是:

>>> flattenTree(sample.asScala.toList)
res0: List[String] = List(1, 3, 4)

这意味着由于某种原因，我丢失了带有键“2”的节点。

有人可以推荐一种正确且更有效的方法来展平这棵树吗？

Answer 1

您未能在每次连续调用时添加累积的 key 。请尝试以下操作:

def flattenTree(tree: List[R]): List[String] = {
  tree.foldLeft(List[String]())((acc, x) =>
             x.key :: flattenTree(x.nodes.asScala.toList) ++ acc)
}

生成结果: List(1, 3, 4, 2) ,

或者，如果正确排序很重要:

def flattenTree(tree: List[R]): List[String] = {
  tree.foldLeft(List[String]())((acc, x) =>
             acc ++ (x.key :: flattenTree(x.nodes.asScala.toList)))
}

生成结果: List(1, 2, 3, 4)