Scala

Question

我有以下对象结构：

case class Node(id:Int,children:List[Node])

示例：

NodeA
    id: 1
    children:[
        NodeA1:
            id: 2
            children:
                NodeA11
                ...
        ]       
        NodeB1:
            id: 3
            children:[]
        NodeC1:
            id: 17
            children: [
                NodeC11:
                    id:11
                    children:[
                        NodeC111:
                            id: 19
                            children: []
                    ]

            ]
        ...

我想创建一个递归循环来获取具有特定 ID 的节点，但我被困在如何保持运行如果找不到 iD 并且对象有任何功能儿童名单上的对象。我的函数仅适用于获取第一个节点（例如：Id = 1）。

这是我正在尝试做的事情：

def getNode(id:Int, node:Node) : Node = {
    var result:Node = null
    if(node.id == id){
      return node
    } else if(node.children.size > 0 ){
      for(children <- node.children){
        result = getNode(id, children)
        if(result.id == id){
          return result
        }
      }
    }
    return result
}

Answer 1

函数 getNode 确实应该 return Option[Node] 来解释 Node 树中缺失的 id 的搜索。

在这种情况下，您可以编写递归调用的选项：

def getNode(id:Int, node:Node): Option[Node] = 
  if (node.id == id) Some(node)
  else node.children.collectFirst(Function.unlift(getNode(id, _)))

在必要的情况下，您不需要检查列表长度：只需 return None/null 在您检查每个 child 的循环之后（或不检查是否有 children).

def getNode(id:Int, node:Node) : Option[Node] = {
  if (node.id == id) Some(node)
  else {
    for (child <- node.children) {
      val result = getNode(id, child)
      // At this point `result` is Some(nodeWeAreLookingFor) 
      // if it is in the subtree of the current `child`
      // or None otherwise
      if (result.isDefined) return result
    }
    None
  }
}

对于Java你当然可以用null替换Option，但是在Scala中这个想法自然地被Option

模仿了

Scala - 递归函数不返回对象

Scala - recursive function not returning the object

recursion