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

Что такое ЛитКод?

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

Мои рутинные задачи по решению задач

Я поставил себе цель решать как минимум 3 задачи в день, и мой способ решения включает в себя iPad, ручку для экранов и приложение Freeform. Я пытаюсь рисовать и думать о решениях, и это очень помогает при отправке кода. На первый взгляд множество задач кажется сложным, но стоит потратить несколько минут на размышление и разработку решения (я рекомендую записать свой мыслительный процесс). Если я не могу найти правильное решение за 30 минут, я просматриваю материалы других разработчиков, чтобы выяснить, где мои ошибки (иногда небольшой шаг, который я забыл в своем коде). Даже если ваше решение достаточно хорошее, я настоятельно рекомендую просмотреть предложения других и подумать о других способах решения этой проблемы (более или менее эффективных).

Задача «Обратить двоичное дерево»

Несколько дней назад я столкнулся с проблемой инвертирования двоичного дерева в LeetCode, хорошо известной проблемой, о которой просили в некоторых интервью, и проблемой, которую я увидел, посещая занятия по структурам данных/алгоритмам в университете. Хотя я никогда не сталкивался с этой проблемой на собеседовании, и мне никогда не приходилось явно инвертировать двоичное дерево в своей работе, знание того, как его инвертировать, дало мне больше опыта в DS, деревьях и алгоритмическом мышлении, а также попрактиковало некоторые методы, такие как рекурсия.
Я рекомендую вам попробовать решить эту проблему, прежде чем читать остальную часть статьи.

Решение

Задача «Обратить двоичное дерево» попросила меня: «По заданному корню двоичного дерева инвертировать дерево и вернуть его корень». (другими словами, мы должны «отзеркалить» дерево). Для отправки решения я использовал язык программирования Java, но для других языков шаги такие же (с небольшими изменениями синтаксиса). Пример ввода и ожидаемый результат показаны ниже:

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

Мы собираемся использовать технику рекурсии для рекурсивного вызова метода invertTree(), передавая некоторую часть дерева в качестве корня. Итак, как требует каждая рекурсия, нам нужно определить условие остановки, при котором стек рекурсии завершит работу и вернет соответствующий результат вызова рекурсии. После этого мы просто инвертируем стороны дерева, присваивая root.left значение, возвращаемое рекурсией, передавая root.right в качестве параметра, и делаем то же самое с root.right, присваивая значение результата рекурсии root.left. Поскольку мы изменяем исходное значение, нам нужна вспомогательная переменная для хранения исходного результата root.left (вероятно, вы реализовали подобный код в университете и назвали его методом swap().

В конце мы возвращаем корень с перевернутыми узлами. Вы можете проверить код ниже:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }

        TreeNode aux = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(aux);

        return root;
    }
}

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