IT + Java

Рекурсия далека от идеала.

Рекурсия чаще всего используется только во время собеседований (а этот цикл статей именно направлен на подгтовку к собеседования). В промышленной разработке её чаще избегают изза потенциальных следующих потенциальных проблем:

• Криво написанная рекурсия может выполняться бесконечно (в "лучшем" случае это приведет к ошибке переполнения стэка). В худшем программа повиснет (особенно если программа однопоточная).

• Изначально чаще всего под стэк выделяется не более 1мб памяти а это значит что рекурсивная функция сможет вызвать саму себя где то от 10 до 20 тысяч раз. (размер можно легко увеличить с помощью параметра -Xss но стоит помнить что у JDK есть ограничения по верхней границе - обычно до 1 ГБ)

• Рекурсия сложна для понимания, особенно новичкам.

• Высокое потребление памяти - каждый раз спуская на уровень ниже мы позволяем сборщику мусора удалить ссылки используемые на верхних уровнях - и это не ошибка тк все объекты используемы выше текущего уровня будут использованы когда мы вернемся "снизу"

Очеред (или Стэк) - популярный подход в решении задач на деревья.

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

• Добавляем корневой элемент в очередь

• Проходим по всем элементам очереди и ранее добавленные узлы

• Если наследники узла не пусты добавляем в очередь опять

Обходим дерево в ширину.

Распечатаем все значения дерева сверху вниз, распечатывая значения на каждом уровне слева направо, как гирлянду.

Что такое очередь и как ей пользоваться?

Для начала познакомимся с интерфейсом очереди (Queue) в Java. Очередь представляет собой FIFO (first in, first out - первый зашёл, первый вышел) структуру. В нашем случае потребуется два метода:

• add - добавить в очередь

• poll - вытащить первого из очереди (элемент который бы добавлен раньше других)

Как именно мы будем выполнять обход дерева?

Обходить дерево мы будем следующим способом:

• Добавим в очередь корневой элемент

• "Вытащим" добавленный элемент и положим в очередь его наследников

• Повторим 1-2 шаги пока в очереди ничего не останется

Изобразим эти действя по шагам:

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

Теперь напишем код описанной выше логике

И так как запомнить данный подход если он попадется на собеседовании? Я бы рекомендовал держать в памяти две вещи:

• условие while (!queue.isEmpty())

• queue.poll() - вытаскивание элемента

В следующих статьях мы будем использовать очередь для решения задач, связанных с деревьями. Кому интересна промышленная разработку приглашаю в котовскую телеграм группу

Инвертируем дерево

Целью является инвертировать дерево. Те для каждого узла нужно поменять местами его левый и правый наследники. Логику надо также применять к наследникам наследников.

Давайте проговорим какие этапы нужно продумать:

• Проитерироватсья по всем узлам рекурсией те нам понадобится функция которая будет вызывать саму себя.

• Нижние пустые null узлы нужно будет проигнорировать

• Для всех остальных узлов нужно выполнить смену ссылок для правого и левого наследников

Решение:

Думаю вам тоже задача показалось довольно простой но при этом она является одной из самых частых во время собеседований. В следующей статье мы рассмотрим более сложные случаи. Всем кому интересно - добро пожаловать в мою группу.

Довольно очевидно что самый длинный узел в данном дереве - M и он является пятым по счету если головной является первым.

Как решать данную задачу используя рекурсию.

Если сильно упрощать то нам нужно сделать 2 действия:

• Обойти все узлы

• Каким то образом "сохранять" состояния каждый раз когда мы обходим узлы

Но как же сохранять состояния о той глубине на которой мы побывали? Тут есть как минимум два варианта:

• Использовать возвращемое значение самой рекурсивной функции и "возвращать" её на уровень выше.

• Иметь какой то объект в котором мы будем сохранять состояния находясь внутри рекурсии

Воспользуемся первым подходом. Сосредоточимся на следующих аспектах:

• Рекурсивная функция должна передавать значение сама себе "наверх"

• Определить какое именно значение должно перебрасываться.

Логика передаваемого "наверх" значения.

• Самые нижние уровни (те что указывают на null) должны возвращать 0 тк они не включены в расчет глубины данного подграфа

• Нижний уровень который с листьями имеет лишь null предков должен вернуть 1 тк он является первым уровнем

• Узел выше чем 1й (те не лист) должен выбирать максимальный уровень из двух его наследников и добавлять 1 тк находится на уровень выше из наибольшего из них.

После данных рассуждений у нас вырисовывается вот такая картина:

К чему привели наши рассуждения?

Все эти рассуждения намекают что в нашей итеративной функциии будет 3 разных сценария и функция которая выбирает наибольшее из двух. Именно подобные размышления чаще всего помогают перевести абстрактные размышления в код.

И так первая версия кода:

Самый важная часть кода - итеративный вызов левого и правого поддерева и последующий расчет максимального значения среди них. И конечно же добавление 1 наибольшему из них чтобы учесть и текущую высоту.

Этот код можно было бы улучшить удалив случай когда мы находимся в самом низу - дело в том что если условие истино то возвращаемое значение maxDepth + 1 будет также равно 1.

Спасибо за внимание, всем кому интересна промышленная разработка приглашаю в мой канал.

Давайте рассмотрим уже знакомое дерево:

Прямой обход дерева (Префиксный) - NLR

В прошло части мы уже итерировались по дереву рекурсивно. В нем мы сначала печатали значение узла (Node) затем посещаем левое поддерево (Left) и лишь потом правое поддерево (Right). Такой подход называется прямым или еще префиксным - NLR.

Центрированный обход дерева (Инфиксный) LNR

Теперь сделаем одно минимальное изменение - сначала мы пойдем в левое поддерево (Left) затем распечатаем значение узла (Node) и потом пойдем в правое поддерево (Right) - этот обход называют Инфиксным (от лат. in внутри fixus закрепленный) или центрированным - LNR. Понятие инфиксный прошло из математики. Если очень упрощать значит что N находится между L и R.

И так вроде рекурсия выполнила ровно такой же обход, но теперь процесс распечатки значения узла мы стали делать после того как уходим "влево". Теперь если задуматься то первая печать произойдет лишь когда мы дойдем до нижнего левого узла. Давайте изобразим как будет выглядеть "обход" а порядок печати значений узлов:

Обратный или Постфиксный обход. LRN

Думаю уже понятно что данный подход подразумевает печать значения узла (Node) после посещения левого (Left) поддерева и правого (Right) поддерева - LRN

Порядок распечатки изображен ниже:

Минимальные изменения - большие последствия.

Изза минимальных изменений (меняя лишь порядок одной строчки) мы получили разные обходы дерева. Это позволит нам решать разные задачи в будущем.

Следующий этап.

В следующей статье мы рассмотрим какие задачи мы можем решать используя описанные подходы. Одна из главных целей цикла статей - помочь преодолеть страх задач про деревья во время собеседований. Думаю стоит повторить еще раз - как только вам прилетела задача на деревья во время собеса начинайте с того что напишите функцию обхода. Большинство алгоритмических задач решается именно через рекурсию (но не только через неё).

Кому интересна промышленная разработка и Java приглашаю в мою группу. Спасибо за внимание.