Scala中如何基于元素-父元素Map生成指定层级序列并避免冗余？

给定一个Map，键为元素，值为该元素的父元素（None表示无父元素），示例如下：

Map(
    "a1" -> Some("b1"), 
    "a2" -> Some("b1"), 
    "b1" -> Some("c1"),
    "c1" -> None
)

需要生成从叶子元素到根元素的完整路径序列，期望输出：

Seq(
    Seq("a1", "b1", "c1"),
    Seq("a2", "b1", "c1")
)

需避免生成包含中间节点路径的冗余结果（如Seq("b1", "c1")、Seq("c1")这类不需要的序列）。

核心思路是只处理叶子节点（即从未出现在Map值中的元素，这类元素没有子节点，是路径的起点），再通过递归/迭代生成每个叶子到根的完整路径。

步骤1：识别叶子节点 #

先筛选出所有不是任何元素父节点的元素，这些就是路径的起始点：

val parentMap = Map(
    "a1" -> Some("b1"), 
    "a2" -> Some("b1"), 
    "b1" -> Some("c1"),
    "c1" -> None
)

// 提取所有存在的父节点（过滤掉None的情况）
val allParents = parentMap.values.flatten.toSet
// 叶子节点 = Map的键中不在父节点集合里的元素
val leafNodes = parentMap.keys.filterNot(allParents.contains).toSeq

此处leafNodes会得到Seq("a1", "a2")，正是我们需要的起始节点。

步骤2：生成单个叶子节点的完整路径 #

编写辅助函数，输入节点后递归遍历父节点，拼接出从该节点到根的完整路径：

def buildPath(node: String): Seq[String] = {
    parentMap(node) match {
        case Some(parent) => node +: buildPath(parent)
        case None => Seq(node)
    }
}

例如调用buildPath("a1")，会返回Seq("a1", "b1", "c1")。

步骤3：批量生成所有叶子节点的路径 #

遍历所有叶子节点，调用辅助函数生成对应路径：

val result = leafNodes.map(buildPath)

最终result即为期望的输出结果。

完整代码示例 #

val parentMap = Map(
    "a1" -> Some("b1"), 
    "a2" -> Some("b1"), 
    "b1" -> Some("c1"),
    "c1" -> None
)

val allParents = parentMap.values.flatten.toSet
val leafNodes = parentMap.keys.filterNot(allParents.contains).toSeq

def buildPath(node: String): Seq[String] = {
    parentMap(node) match {
        case Some(parent) => node +: buildPath(parent)
        case None => Seq(node)
    }
}

val result = leafNodes.map(buildPath)
// 输出: Seq(Seq("a1", "b1", "c1"), Seq("a2", "b1", "c1"))

冗余规避说明 #

因为我们仅从叶子节点开始生成路径，中间节点（如b1、c1）本身是其他节点的父节点，不会被当作起始点，自然不会生成它们的单独路径，彻底避免了冗余结果。

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