Scala递归函数内List拼接不生效 二叉树去重算法问题求助

问题根因 #

Scala 标准库中的List是不可变集合，x :: found操作不会修改原有found列表的内容，只会生成一个头部追加了x的新列表。你当前代码中执行x::found后没有将新生成的列表赋值给变量，也没有传递给后续递归调用，该操作的结果被直接丢弃，外层传入的found始终是初始的空列表，所以看起来拼接操作没有生效。

除此之外你当前的代码结构也存在问题：内部递归函数dfs_helper没有携带更新后的已发现元素集合，所有递归分支共用最外层传入的不变found，自然无法感知到本次遍历新增的元素，也无法正确判断后续节点是否重复。

修复方案 #

你可以调整dfs_helper的定义，让它接收当前的已发现元素列表作为参数，同时返回处理后的二叉树和更新后的已发现元素集合，保证遍历过程中新增的元素可以被后续递归分支感知到，参考实现如下：

def removeRecurring_dfs(bt: BT): BT = {
  // 辅助函数入参携带当前已发现的元素，返回值同时返回更新后的已发现元素
  def dfs_helper(tree: BT, found: List[Int]): (BT, List[Int]) = {
    tree match
      case Empty => (Empty, found)
      case Node(x, _, _) if found.contains(x) => 
        // 移除重复节点后继续遍历，已发现集合不变
        dfs_helper(rR(tree), found)
      case Node(x, left, right) =>
        // 生成新的已发现集合
        val updatedFound = x :: found
        // 先处理左子树，拿到左子树处理结果和左遍历后的已发现集合
        val (processedLeft, leftFound) = dfs_helper(left, updatedFound)
        // 用左遍历更新后的集合处理右子树
        val (processedRight, finalFound) = dfs_helper(right, leftFound)
        // 返回构造的新节点和最终的已发现集合
        (Node(x, processedLeft, processedRight), finalFound)
  }
  def rR(tree: BT): BT = removeNode(tree, findPath(tree))
  // 初始调用传入空集合，只取处理后的二叉树结果
  dfs_helper(bt, Nil)._1
}

额外优化提示 #

如果你的二叉树节点数量较多，List的contains操作时间复杂度为O(n)，会导致整体算法效率偏低，你可以将found替换为scala.collection.mutable.HashSet，既可以保留修改集合的能力，也能把重复判断的时间复杂度降到O(1)。

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