Задачник по алгоритмам

Программа курса:

Задача 17: Обход двоичного дерева

Напишите функцию def traversal(root), которая принимает двоичное дерево, представленное в виде вложенных списков, и возвращает значения узлов в порядке последовательного обхода (in-order traversal).

Бинарное дерево представляется в виде вложенных списков:

  • Узел дерева имеет вид [значение, левое_поддерево, правое_поддерево].
  • Если у узла нет поддерева, оно заменяется на None.
  • Пустое дерево задаётся как пустой список [].

Последовательный обход (in-order traversal) предполагает следующий порядок:

  1. Рекурсивно обойти левое поддерево.
  2. Посетить текущий узел (добавить его значение в результат).
  3. Рекурсивно обойти правое поддерево.

Примеры представления дерева:

  1. Дерево:

        1
     \
      2
     /
    3

    представляется как: [1, None, [2, [3, None, None], None]].

  2. Дерево:

            1
      /   \
     2     3
    / \      \
   4   5      8
      / \    /
     6   7  9

    представляется как: [1, [2, [4, None, None], [5, [6, None, None], [7, None, None]]], [3, None, [8, [9, None, None], None]]].

Формат входных данных:

  • root — список, представляющий корень двоичного дерева в формате [значение, левое_поддерево, правое_поддерево].
    • Узлы без детей задаются как None.
    • Пустое дерево представляется как пустой список [].

Формат выходных данных:

  • Список значений узлов в порядке последовательного обхода.

Примеры

Пример 1:

Ввод:
root = [1, None, [2, [3, None, None], None]]

Вывод:
[1, 3, 2]

Пример 2:

Ввод:
root = [1, [2, [4, None, None], [5, [6, None, None], [7, None, None]]], [3, None, [8, [9, None, None], None]]]

Вывод:
[4, 2, 6, 5, 7, 1, 3, 9, 8]

Пример 3:

Ввод:
root = []

Вывод:
[]

Пример 4:

Ввод:
root = [1]

Вывод:
[1]

0
Вы должны Войти или Зарегистрироваться чтобы оставлять комментарии