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

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

Задача 13: Инвертирование двоичного дерева

Напишите определение функции def invertTree(root), которая принимает корень root бинарного дерева и инвертирует его, возвращая новый корень дерева.

Пример представления бинарного дерева:

Бинарное дерево — это структура данных, состоящая из узлов, где каждый узел имеет два дочерних узла: левый и правый. Каждый узел может содержать некоторое значение, а также ссылки на свои дочерние элементы.

Пример представления узла бинарного дерева:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val  # Значение узла
        self.left = left  # Ссылка на левый дочерний узел
        self.right = right  # Ссылка на правый дочерний узел

Этот класс невидим и он заготовлен в вашем коде.

Пример 1

Ввод:

root = [4,2,7,1,3,6,9]

Дерево до инвертирования:

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

Вывод:

[4,7,2,9,6,3,1]

Дерево после инвертирования:

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

Пример 2

Ввод:

root = [2,1,3]

Дерево до инвертирования:

      2
     / \
    1   3

Вывод:

[2,3,1]

Дерево после инвертирования:

      2
     / \
    3   1

Пример 3

Ввод:

root = []

Дерево до инвертирования:

(Пустое дерево)

Вывод:

[]

Дерево после инвертирования:

(Пустое дерево)

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