Как отразить бинарное дерево?

Question

Мне нужно отразить бинарное дерево в Scala.Я думаю, что это должно работать так:

sealed trait BT[+A]
case object Empty extends BT[Nothing]
case class Node[+A](elem:A, left:BT[A], right:BT[A]) extends BT[A]

def mirrorTree[A](bt: BT[A]): BT[A] = bt match {
  case Empty => Empty
  case Node(root, left, right) => Node(root, right, left)
}

val t = Node(1,Node(2,Empty,Node(3,Empty,Empty)),Empty)
mirrorTree(t)

Но это возвращает меня только поменявшись местами первого уровня, я должен вызывать функцию рекурсивным способом для левого и правого поддерева, но я не знаю, как это сделатьесли я должен вернуть дерево из функции, поэтому я не могу использовать операторы, как для списков.

Answer 1

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

sealed trait BT[+A]
case object Empty extends BT[Nothing]
case class Node[+A](elem:A, left:BT[A], right:BT[A]) extends BT[A]

def mirrorTree[A](bt: BT[A]): BT[A] = bt match {
  case Empty => Empty
  case Node(root, left, right) => 
    val newLeft = mirrorTree(right) 
    val newRight = mirrorTree(left)
    Node(root, newLeft,newRight)
}

val t = Node(1,Node(2,Empty,Node(3,Empty,Node(4,Empty,Empty))),Empty)


mirrorTree(t)  // Node(1,Empty,Node(2,Node(3,Node(4,Empty,Empty),Empty),Empty))

Answer 2

Если вы хотите отразить все это, выполните:

case Node(root, left, right) => Node(root, mirrorTree(right), mirrorTree(left))