Эта часть является продолжением цикла лекций про деревья. В этой части мы снова воспользуемся рекурсией чтобы инвертировать дерево. Задача довольно популярна и по сложности является довольно простой.
Допустим у нас есть дерево
Допустим у нас есть дерево ниже:
Инвертируем дерево
Целью является инвертировать дерево. Те для каждого узла нужно поменять местами его левый и правый наследники. Логику надо также применять к наследникам наследников.
Давайте проговорим какие этапы нужно продумать:
- Проитерироватсья по всем узлам рекурсией те нам понадобится функция которая будет вызывать саму себя.
- Нижние пустые null узлы нужно будет проигнорировать
- Для всех остальных узлов нужно выполнить смену ссылок для правого и левого наследников
Решение:
Думаю вам тоже задача показалось довольно простой но при этом она является одной из самых частых во время собеседований. В следующей статье мы рассмотрим более сложные случаи. Всем кому интересно - добро пожаловать в мою группу.