当前位置：首页 > article >正文

【scala】含有list子集的递归方法记录层数深度

article 2025/1/16 7:02:36

样例使用scala语言编写。
特点：
RecursiveData对象中包含一个成员child含有多个RecursiveData子对象。

思路：
递归方法中传入一个：int作为parent的深度，传入一个set记录所以深度集合。

同一深度int+1不会影响相同深度的结果，set又可以将统一深度层去重。

容易犯错误：使用单独对象记录，应为是递归是树形结构，随着层数和枝叶增加，会多计算，如recWrong方法就是错误典型。

import org.scalatest.funsuite.AnyFunSuite

import java.util.concurrent.atomic.AtomicInteger
import scala.collection.mutable

case class RecursiveData(name: String, child: List[RecursiveData])

class RecursiveTest extends AnyFunSuite {

  val r41 = RecursiveData("41", List.empty)
  val r42 = RecursiveData("42", List.empty)
  val r43 = RecursiveData("43", List.empty)
  val r44 = RecursiveData("44", List.empty)
  val r31 = RecursiveData("31", List(r41, r42))
  val r32 = RecursiveData("32", List(r43, r44))
  val r33 = RecursiveData("33", List.empty)
  val r34 = RecursiveData("34", List.empty)
  val r35 = RecursiveData("35", List.empty)
  val r36 = RecursiveData("36", List.empty)
  val r37 = RecursiveData("37", List.empty)
  val r21 = RecursiveData("21", List(r31, r32, r33))
  val r22 = RecursiveData("22", List(r34, r35))
  val r23 = RecursiveData("23", List(r36, r37))
  val r11 = RecursiveData("11", List(r21, r22, r23))

  def rec(data: RecursiveData, parentDepth: Int, depths: mutable.Set[Integer]): Unit = {
    val currDepth = parentDepth + 1
    depths.add(currDepth)
    data.child.foreach(c => {
      rec(c, currDepth, depths)
    })
  }

  test("test-recursive-right") {
    val depths: mutable.Set[Integer] = mutable.Set.empty
    rec(r11, 0, depths)
    println(s"current depths:${depths},and max depths:${depths.max}")
    // current depths:Set(1, 2, 3, 4),and max depths:4
  }

  def recWrong(data: RecursiveData, depth: AtomicInteger): Unit = {
    data.child.foreach(c => {
      recWrong(c, depth)
    })
    if (data.child.nonEmpty) {
      // 错误思路: 每次增加减去相应的子成员增加量
      depth.set(depth.get() - (data.child.size - 1))
    }
    depth.getAndIncrement()
  }

  test("test-recursive-wrong") {
    val depth: AtomicInteger = new AtomicInteger
    recWrong(r11, depth)
    println(depth)
    // 7
  }
}