Условие задачи

Даны два массива целых чисел preorder и inorder, где preorder является обходом дерева в прямом порядке, а inorder - в порядке следования узлов. Постройте и верните бинарное дерево.

Входные данные

• preorder - массив целых чисел, содержащий обход дерева в прямом порядке, где первый элемент - корень дерева.
• inorder - массив целых чисел, содержащий обход дерева в порядке следования узлов.

Выходные данные

• Бинарное дерево, построенное по заданным обходам.

Примеры

Пример 1

Входные данные:

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Выходные данные:

     3
    / \\\\
   9  20
     /  \\\\
    15   7

Пример 2

Входные данные:

preorder = [1,2]
inorder = [2,1]

Выходные данные:

   1
  /
 2

Решение

1. Найдем корень дерева в массиве preorder. Он же будет первым элементом этого массива.