Друзья! Думаю многие мои давние читатели помнят о цикле статей "сам себе экосистема", где я стараюсь вдохнуть новую жизнь в девайсы 10+ летней давности путем разработки собственных клиентов нужных мне сервисов! Уже вышло две статьи из этой рубрики ( Сам себе экосистема: Как я адаптировал старый смартфон под современные реалии и написал клиенты нужных мне сервисов Не дадим Windows Phone умереть! Как я написал свои клиенты VK, YouTube для Nokia Lumia? Сам себе экосистема ч.2 ). Сейчас, вот, держу несколько своих девайсов на Android 2.2 и потихоньку пилю наработки ещё нескольких нужных мне приложений: клиент Сбера на СМСках (по сути, удобная обертка над 900 с виджетами), актуальная погода на неделю вперед, вьювер карт OpenStreetMap и трекинг посылок. ВКшечка и ютубчик, как мы помним, уже есть. Давайте устроим голосование, не одному ли мне это интересно и быть ли третьей статье из рубрики "сам себе экосистема"?

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

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

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

• Изначально чаще всего под стэк выделяется не более 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.

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