Scala，列表附加在递归函数中不起作用

Question

所以我正在研究一种采用二进制树的算法：

sealed trait BT
case object Empty extends BT
case class Node(val x: Int, val left: BT, val right: BT) extends BT

并借助递归dfs搜索树，返回没有重复的二叉树。

def removeRecurring_dfs(bt: BT, found: List[Int]): BT = {
def dfs_helper(tree: BT): BT = {
tree match
case Empty => Empty
case Node(x, _, _) if found.contains(x) => dfs_helper(rR(tree))
case Node(x, Empty, Empty) =>
x::found
tree
case Node(x, left, Empty) =>
x::found
Node(x, dfs_helper(left), Empty)
case Node(x, Empty, right) =>
x::found
Node(x, Empty, dfs_helper(right))
case Node(x, left, right) =>
x::found
Node(x, dfs_helper(left), dfs_helper(right))
}
def rR(tree: BT): BT = removeNode(tree, findPath(tree))
dfs_helper(bt)
}

列表"found"最初为空removeNode和findPath是帮助我实现目标的函数。经过一些测试，我发现

x::found

即使触发了该行的case，该行也永远不会工作。通过一些printin操作，结果发现模式匹配如我所愿。

我最近开始玩scala，我不明白是什么导致了的这种行为

Answer 1

正如已经指出的，List是不可变的，因此x :: found创建了一个新的List，其中元素x预先添加到found列表中。

新的List必须保存/发送到某个地方，否则它将丢失并被垃圾收集。

我不知道你的findPath()和removeNode()方法应该做什么，所以这有点难说，但看起来这就是你想要实现的。(标量-3语法(

sealed trait BT
case object Empty extends BT
case class Node(x: Int, left: BT, right: BT) extends BT
def removeRecurring_dfs(bt: BT): BT =
def dfs_helper(tree:BT, found:Set[Int]): (BT,Set[Int]) = tree match
case Empty => (Empty, found)
case Node(x, left, right) =>
if found(x) then
dfs_helper(rR(tree), found)
else
val (lftNode, moreFound)  = dfs_helper(left, found + x)
val (rgtNode, totalFound) = dfs_helper(right, moreFound)
(Node(x, lftNode, rgtNode), totalFound)
def rR(tree: BT): BT = removeNode(tree, findPath(tree))
dfs_helper(bt, Set())._1