如何从边集合构建有根有向树且避免栈溢出？附Scala实现问询

首先得提个小问题：你给出的parentToChild: Map[String, String]参数有点不太贴合需求——Scala的Map键是唯一的，这意味着每个父节点只能绑定一个子节点，和题目里“父节点可拥有任意数量子节点”的要求矛盾。所以我先把参数调整成更合理的parentToChild: Map[String, Seq[String]]（每个父节点对应一个子节点列表），如果你的原始输入是边的集合（比如Seq[(String, String)]），我也加了个辅助函数帮你转成这种映射。

接下来聊核心问题：普通递归处理深度极大的树时，很容易因为调用栈过深触发StackOverflowError。要解决这个问题，我们得换个思路——用迭代的方式构建树，比如基于拓扑排序从叶子到根逐步构建，完全避开递归调用。

实现思路 #

我们采用拓扑排序+迭代构建的方案，步骤如下：

1. 预处理输入，得到父到子的映射，以及反向的子到父的映射（用于回溯父节点）。
2. 计算每个节点的出度（即子节点的数量），出度为0的节点是叶子节点。
3. 从叶子节点开始迭代构建：叶子节点没有子节点，直接创建；当一个父节点的所有子节点都构建完成后，再创建该父节点并关联已构建的子节点。
4. 最终返回根节点的实例。

Scala代码实现 #

import scala.collection.mutable

case class Node(name: String, children: Seq[Node])

def constructTree(root: String, parentToChild: Map[String, Seq[String]]): Node = {
  // 确保父节点映射的默认值为空列表，避免空指针
  val childMap: Map[String, Seq[String]] = parentToChild.withDefaultValue(Seq.empty)
  
  // 构建子节点到父节点的反向映射，用于后续回溯父节点
  val childToParent: Map[String, String] = parentToChild.flatMap { case (parent, children) =>
    children.map(child => child -> parent)
  }.toMap
  
  // 收集所有节点的名称：根节点 + 所有父节点 + 所有子节点
  val allNodes = (Set(root) ++ childMap.keys ++ childMap.values.flatten).toList
  
  // 初始化可变的出度映射，用于跟踪每个节点还有多少子节点未构建
  val outDegree = mutable.Map.empty[String, Int]
  allNodes.foreach(node => outDegree(node) = childMap(node).size)
  
  // 初始化队列，先放入所有出度为0的叶子节点
  val queue = mutable.Queue.empty[String]
  outDegree.filter(_._2 == 0).keys.foreach(queue.enqueue)
  
  // 保存已构建完成的节点
  val builtNodes = mutable.Map.empty[String, Node]
  
  // 迭代处理队列中的节点
  while (queue.nonEmpty) {
    val currentNodeName = queue.dequeue()
    
    // 构建当前节点：如果是叶子节点，children为空；否则是已构建的子节点列表
    val children = childMap(currentNodeName).map(builtNodes(_))
    builtNodes(currentNodeName) = Node(currentNodeName, children)
    
    // 找到当前节点的父节点（如果存在）
    childToParent.get(currentNodeName).foreach { parentName =>
      // 父节点的出度减1，表示一个子节点已构建完成
      outDegree(parentName) -= 1
      
      // 如果父节点的所有子节点都已构建，就把父节点加入队列等待处理
      if (outDegree(parentName) == 0) {
        queue.enqueue(parentName)
      }
    }
  }
  
  // 返回根节点
  builtNodes(root)
}

// 辅助函数：如果你的原始输入是边的列表（Seq[(String, String)]），可以用这个函数转换成父到多子的映射
def edgesToParentMap(edges: Seq[(String, String)]): Map[String, Seq[String]] = {
  edges.groupBy(_._1).mapValues(_.map(_._2))
}

为什么不会栈溢出？ #

整个构建过程完全是迭代式的，没有使用递归调用：我们用队列来管理待处理的节点，所有节点的创建和关联都在循环中完成，不会产生深度嵌套的调用栈，因此即使树的深度达到几万甚至几十万层，也不会出现栈溢出问题。

使用示例 #

// 示例边集合：根节点是"root"
val edges = Seq(
  ("root", "a"),
  ("root", "b"),
  ("a", "c"),
  ("a", "d"),
  ("d", "e")
)

// 转换成父到子的映射
val parentMap = edgesToParentMap(edges)

// 构建树
val tree = constructTree("root", parentMap)

// 打印树结构验证
def printTree(node: Node, indent: String = ""): Unit = {
  println(s"$indent${node.name}")
  node.children.foreach(child => printTree(child, indent + "  "))
}

printTree(tree)

输出结果：

root
  a
    c
    d
      e
  b

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