Как рекурсивно разобрать это древовидную структуру?

Question

Рассмотрим древовидную структуру данных со следующим определением узла -

Node(id:Int, parent: Int, name:Option[String])

У меня есть List [Node], где Node n с тем же родителем может иметь одинаковый идентификатор.Я хочу создать новый Список [Узел], чтобы каждый Узел имел уникальный идентификатор.Можно переписать id и parent каждого узла для формирования списка вывода.Мне не нужен точный код, просто нужны подсказки, чтобы написать рекурсивное решение

Пример -

Ввод - List(Node(5, 0, "a"), Node(2, 5,"b"), Node(2, 5, "c"), Node(3,5, "d"), Node(4, 3,"e"))

Вывод - List(Node(1, 0, "a"), Node(2, 1, "b"), Node(3, 1, "c"), Node(4, 1, "d"), Node(5, 4, "e"))

Answer 1

Таким образом, мы не можем перенумеровать ни один дочерний узел, пока не узнаем новый id родительского узла. Нетривиальная задача.

case class Node(id:Int, parent: Int, name:String)

def renum(in   :List[Node]
         ,seen :Map[Int,Int] = Map(0 -> 0)
         ,acc  :List[Node]   = Nil
         ,hold :List[Node]   = Nil) :List[Node] = in match {
  case Nil =>                                            //are we done?
    if (hold.isEmpty) acc.reverse else renum(hold, seen, acc)
  case Node(id,par,nm) :: ns if seen.isDefinedAt(par) => //parent was processed
    val newId = acc.size + 1
    renum(ns, seen+(id->newId), Node(newId,seen(par),nm)::acc, hold)
  case n :: ns =>                                        //put node on hold
    renum(ns, seen, acc, n::hold)
}

Тестирование:

/*
     a 
   / | \
   b c d
       |
       e
*/
val input = List(Node(5,0,"a"),Node(2,5,"b"),Node(2,5,"c"), Node(3,5,"d"),Node(4,3,"e"))

renum(util.Random.shuffle(input))
renum(util.Random.shuffle(input))
renum(util.Random.shuffle(input))
renum(util.Random.shuffle(input))
renum(util.Random.shuffle(input))
//res0: List[Node] = List(Node(1,0,a), Node(2,1,c), Node(3,1,b), Node(4,1,d), Node(5,4,e))
//res1: List[Node] = List(Node(1,0,a), Node(2,1,b), Node(3,1,d), Node(4,1,c), Node(5,3,e))
//res2: List[Node] = List(Node(1,0,a), Node(2,1,b), Node(3,1,d), Node(4,3,e), Node(5,1,c))
//res3: List[Node] = List(Node(1,0,a), Node(2,1,b), Node(3,1,c), Node(4,1,d), Node(5,4,e))
//res4: List[Node] = List(Node(1,0,a), Node(2,1,b), Node(3,1,c), Node(4,1,d), Node(5,4,e))