C/C++ | LeetCode

Задача: 920. Number of Music Playlists Сложность: hard В вашем плеере есть n разных песен. Во время путешествия вы хотите прослушать goal песен (не обязательно разных). Чтобы избежать скуки, вы создадите плейлист таким образом, чтобы: каждая песня играла хотя бы один раз. Песня может быть проиграна снова только в том случае, если было проиграно k других песен. Учитывая n, цель и k, верните количество возможных плейлистов, которые вы можете создать. Поскольку ответ может быть очень большим, верните его по модулю 10^9 + 7. Пример:

Input: n = 3, goal = 3, k = 1
Output: 6

👨‍💻 Алгоритм: 1⃣Создать двумерный массив dp, где dp[i][j] представляет количество возможных плейлистов длины i, содержащих j различных песен. 2⃣Инициализировать dp[0][0] = 1, что означает, что существует один способ создать плейлист длины 0 с 0 песнями. Заполнить массив dp, используя два случая: Добавление новой песни, которая не была проиграна раньше: dp[i][j] += dp[i-1][j-1] * (n - j + 1) Повторное проигрывание песни, если было проиграно k других песен: dp[i][j] += dp[i-1][j] * max(j - k, 0) 3⃣Ответ находится в dp[goal][n]. 😎 Решение:

class Solution {
public:
    int numMusicPlaylists(int n, int goal, int k) {
        const int MOD = 1'000'000'007;
        vector<vector<long>> dp(goal + 1, vector<long>(n + 1, 0));
        dp[0][0] = 1;

        for (int i = 1; i <= goal; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j-1] * (n - j + 1) % MOD;
                if (j > k) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j] * (j - k) % MOD) % MOD;
                }
            }
        }

        return dp[goal][n];
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1214. Two Sum BSTs Сложность: medium Даны корни двух бинарных деревьев поиска, root1 и root2, верните true, если и только если существует узел в первом дереве и узел во втором дереве, значения которых в сумме равны заданному целому числу target. Пример:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
Output: false

👨‍💻 Алгоритм: 1⃣Создайте два пустых множества node_set1 и node_set2. Выполните обход дерева root1, добавляя значения каждого узла в node_set1, и выполните обход дерева root2, добавляя значения каждого узла в node_set2. 2⃣Итерация по элементам в node_set1: для каждого элемента value1 проверяйте, находится ли target - value1 в node_set2. 3⃣Если target - value1 находится в node_set2, верните true. Если после завершения итерации не найдено ни одной подходящей пары, верните false. 😎 Решение:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
    void dfs(TreeNode* node, unordered_set<int>& nodeSet) {
        if (!node) return;
        dfs(node->left, nodeSet);
        nodeSet.insert(node->val);
        dfs(node->right, nodeSet);
    }

public:
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        unordered_set<int> nodeSet1, nodeSet2;
        dfs(root1, nodeSet1);
        dfs(root2, nodeSet2);
        
        for (int value1 : nodeSet1) {
            if (nodeSet2.count(target - value1)) {
                return true;
            }
        }
        
        return false;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 263. Ugly Number Сложность: easy Уродливое число — это положительное целое число, простые множители которого только 2, 3 и 5. Верните true, если n — уродливое число. Пример:

Input: n = 6 Output: true

👨‍💻 Алгоритм: 1⃣Проверяем, является ли число положительным. Если n <= 0, сразу возвращаем false, так как уродливыми считаются только положительные числа. 2⃣Создаём функцию keepDividingWhenDivisible, которая делит n на factor, пока результат делится без остатка. 3⃣Последовательно делим n на 2, 3 и 5. Если после всех делений n == 1, значит других множителей не было — число уродливое. 😎 Решение:

class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0) {
            return false;
        }
        for (auto factor : {2, 3, 5}) {
            n = keepDividingWhenDivisible(n, factor);
        }
        return n == 1;
    }

private:
    int keepDividingWhenDivisible(int dividend, int divisor) {
        while (dividend % divisor == 0) {
            dividend /= divisor;
        }
        return dividend;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 815. Bus Routes Сложность: hard Дан массив routes, представляющий автобусные маршруты, где routes[i] - это автобусный маршрут, который i-й автобус повторяет бесконечно. Например, если routes[0] = [1, 5, 7], это означает, что 0-й автобус путешествует в последовательности 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... бесконечно. Вы начинаете на автобусной остановке source (вы изначально не находитесь в автобусе) и хотите добраться до автобусной остановки target. Перемещаться между автобусными остановками можно только на автобусах. Верните наименьшее количество автобусов, которые вам нужно взять, чтобы доехать от source до target. Верните -1, если это невозможно. Пример:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

👨‍💻 Алгоритм: 1⃣Верните 0, если source и target совпадают. Инициализируйте пустую карту adjList, чтобы хранить ребра, где ключ - это автобусная остановка, а значение - список целых чисел, обозначающих индексы маршрутов, которые имеют эту остановку. Инициализируйте пустую очередь q и неупорядоченное множество vis, чтобы отслеживать посещенные маршруты. Вставьте начальные маршруты в очередь q и отметьте их посещенными в vis. 2⃣Итерация по очереди, пока она не пуста: извлеките маршрут из очереди, итерируйтесь по остановкам в маршруте. Если остановка равна target, верните busCount. В противном случае, итерируйтесь по маршрутам для этой остановки в карте adjList, добавьте непосещенные маршруты в очередь и отметьте их посещенными. 3⃣Верните -1 после завершения обхода в ширину (BFS). 😎 Решение:

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) return 0;

        unordered_map<int, vector<int>> adjList;
        for (int route = 0; route < routes.size(); route++) {
            for (int stop : routes[route]) {
                adjList[stop].push_back(route);
            }
        }

        queue<int> q;
        unordered_set<int> vis;
        for (int route : adjList[source]) {
            q.push(route);
            vis.insert(route);
        }

        int busCount = 1;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int route = q.front();
                q.pop();

                for (int stop : routes[route]) {
                    if (stop == target) return busCount;

                    for (int nextRoute : adjList[stop]) {
                        if (!vis.count(nextRoute)) {
                            vis.insert(nextRoute);
                            q.push(nextRoute);
                        }
                    }
                }
            }
            busCount++;
        }
        return -1;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Курс "Дизайн карточек для WB и Ozon". Бесплатно и с нуля Дизайнер карточек для маркетплейсов — востребованная и доходная профессия 💰 Научись ей бесплатно! - Бесплатный доступ - Разбор ДЗ от наставника - Мощные кейсы в портфолио Зарегистрироваться #реклама 16+ yudaevschool24.online О рекламодателе

Задача: 1032. Stream of Characters Сложность: hard Разработайте алгоритм, который принимает поток символов и проверяет, является ли суффикс этих символов строкой заданного массива строк words. Например, если words = ["abc", "xyz"] и в поток добавлены четыре символа (один за другим) 'a', 'x', 'y' и 'z', ваш алгоритм должен определить, что суффикс "xyz" символов "axyz" соответствует "xyz" из words. Реализуйте класс StreamChecker: StreamChecker(String[] words) Инициализирует объект с массивом строк words. boolean query(char letter) Принимает новый символ из потока и возвращает true, если любой непустой суффикс из потока образует слово, которое есть в words. Пример:

Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]

👨‍💻 Алгоритм: 1⃣Построение суффиксного Trie: Создайте суффиксный Trie (префиксное дерево) для хранения всех слов из массива words в обратном порядке. Это позволяет эффективно искать слова, которые являются суффиксами потока символов. 2⃣Проверка суффиксов: Для каждого нового символа, проходите по текущему списку символов и проверяйте, образуют ли они какой-либо суффикс, присутствующий в Trie. Если найдено совпадение, возвращайте true, иначе продолжайте добавлять новые символы и проверять суффиксы. 3⃣Сравнение двух случаев: Рассмотрите оба случая: подмассив длины firstLen до подмассива длины secondLen и подмассив длины secondLen до подмассива длины firstLen. Найдите максимальную сумму для каждого случая. 😎 Решение:

class TrieNode {
public:
    TrieNode* children[26] = {};
    bool is_end_of_word = false;
};

class StreamChecker {
public:
    StreamChecker(vector<string>& words) {
        root = new TrieNode();
        for (const string& word : words) {
            TrieNode* node = root;
            for (int i = word.size() - 1; i >= 0; --i) {
                if (!node->children[word[i] - 'a']) {
                    node->children[word[i] - 'a'] = new TrieNode();
                }
                node = node->children[word[i] - 'a'];
            }
            node->is_end_of_word = true;
        }
    }
    
    bool query(char letter) {
        stream.push_front(letter);
        TrieNode* node = root;
        for (char c : stream) {
            if (!node->children[c - 'a']) return false;
            node = node->children[c - 'a'];
            if (node->is_end_of_word) return true;
        }
        return false;
    }

private:
    TrieNode* root;
    deque<char> stream;
};

Ставь 👍 и забирай 📚 Базу знаний

Высшее образование дистанционно в Московском ВУЗе Вы мечтаете получить высшее образование, но не сдали ЕГЭ или получили низкие баллы? У нас есть решение для вас! Институт Международных Экономических Связей предлагает дистанционное обучение , которое позволяет получать качественные знания из любой точки мира по 10+ направлениям обучения. ✅ Государственный диплом без отметки о дистанте ✅ Удобный личный кабинет студента ✅ Поддержка кураторов на каждом этапе обучения ✅ Можно поступить без ЕГЭ Узнать больше #реклама 16+ imes.su О рекламодателе

Задача: 926. Flip String to Monotone Increasing Сложность: medium Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0. Пример:

Input: s = "00110"
Output: 1

👨‍💻 Алгоритм: 1⃣Создать массив left для подсчета количества операций, чтобы сделать подстроку до текущего индекса монотонной (только 0). 2⃣Создать массив right для подсчета количества операций, чтобы сделать подстроку после текущего индекса монотонной (только 1). Пройти по строке и заполнить массивы left и right. 3⃣Пройти по строке и найти минимальное количество операций, чтобы сделать всю строку монотонной. 😎 Решение:

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int n = s.size();
        vector<int> left(n + 1, 0);
        vector<int> right(n + 1, 0);
        
        for (int i = 0; i < n; i++) {
            left[i + 1] = left[i] + (s[i] == '1' ? 1 : 0);
        }
        
        for (int i = n - 1; i >= 0; i--) {
            right[i] = right[i + 1] + (s[i] == '0' ? 1 : 0);
        }
        
        int result = INT_MAX;
        for (int i = 0; i <= n; i++) {
            result = min(result, left[i] + right[i]);
        }
        return result;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Бесплатный доступ к MBA Intensive – для руководителей В Школе Генерального Директора сегодня открыт бесплатный доступ на 2 дня к полноценному онлайн-курсу MBA Intensive при переходе из поста. Вы сможете пройти 500+ практических уроков совершенно бесплатно и улучшить управленческие навыки и понимание бизнес-процессов. После сдачи тестов доступен сертификат о прохождении уроков. Вот какие темы вы успеете изучить – выбирайте любую и приступайте прямо сейчас: 1. Лидерство, личная эффективность и эмоциональный интеллект 2. Управление персоналом 3. Финансы и экономика 4. Торговля и сервис 5. Операционная деятельность и принятие решений 6. Project management 7. Управление маркетингом Оставляйте заявку по ссылке >>> Подать заявку #реклама 16+ gd.ru О рекламодателе

Задача: 848. Shifting Letters Сложность: medium Вам дана строка s из строчных букв английского алфавита и целочисленный массив shifts такой же длины. Назовем shift() буквы следующей буквой в алфавите (с переходом так, что 'z' становится 'a'). Например, shift('a') = 'b', shift('t') = 'u', и shift('z') = 'a'. Теперь для каждого shifts[i] = x мы хотим сдвинуть первые i + 1 букв строки s на x раз. Верните итоговую строку после применения всех таких сдвигов к s. Пример:

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.

👨‍💻 Алгоритм: 1⃣Вычислите общее количество сдвигов для всех символов строки, используя массив shifts. 2⃣Пройдите по строке s и примените вычисленные сдвиги к каждому символу, начиная с первого и уменьшая количество сдвигов на текущем шаге. 3⃣Постройте и верните итоговую строку после всех сдвигов. 😎 Решение:

class Solution {
public:
    string shiftingLetters(string S, vector<int>& shifts) {
        string ans;
        int X = 0;
        for (int shift : shifts)
            X = (X + shift) % 26;

        for (int i = 0; i < S.size(); ++i) {
            int index = S[i] - 'a';
            ans += (char) ((index + X) % 26 + 97);
            X = (X - shifts[i] + 26) % 26;
        }

        return ans;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

Задача: 235. Lowest Common Ancestor of a Binary Search Tree Сложность: medium Дано бинарное дерево поиска (BST). Найдите наименьший общий предок (LCA) двух заданных узлов в BST. Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)." Пример:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

👨‍💻 Алгоритм: 1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Проверьте, находятся ли узлы p и q в правом или левом поддереве текущего узла. 2⃣Продолжение поиска в поддереве: Если оба узла p и q находятся в правом поддереве текущего узла, продолжайте поиск в правом поддереве, начиная с шага 1. Если оба узла p и q находятся в левом поддереве текущего узла, продолжайте поиск в левом поддереве, начиная с шага 1. 3⃣Нахождение LCA: Если узлы p и q находятся в разных поддеревьях относительно текущего узла или один из узлов равен текущему узлу, то текущий узел является наименьшим общим предком (LCA). Верните этот узел как результат. 😎 Решение:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int parentVal = root->val;
        int pVal = p->val;
        int qVal = q->val;

        if (pVal > parentVal && qVal > parentVal) {
            return lowestCommonAncestor(root->right, p, q);
        } else if (pVal < parentVal && qVal < parentVal) {
            return lowestCommonAncestor(root->left, p, q);
        } else {
            return root;
        }
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Приглашаем на Yandex Neuro Scale В этом году главная конференция Yandex Cloud объединит разработчиков, архитекторов, инженеров и IT-руководителей, чтобы обменяться опытом и увидеть, как работают технологии, которые меняют индустрии. 7 тематических треков, 50+ докладов, реальные бизнес-кейсы и нетворкинг! ✨Участие бесплатное, нужно только зарегистрироваться!✨ Зарегистрироваться #реклама 16+ scale.yandex.cloud О рекламодателе Реклама на Яндексе

Задача: 1328. Break a Palindrome Сложность: medium Дана палиндромная строка из строчных английских букв palindrome. Замените ровно один символ на любую строчную английскую букву так, чтобы результирующая строка не была палиндромом и чтобы она была лексикографически наименьшей из возможных. Верните получившуюся строку. Если нет способа заменить символ, чтобы строка перестала быть палиндромом, верните пустую строку. Строка a лексикографически меньше строки b (одинаковой длины), если в первой позиции, где они отличаются, у строки a символ строго меньше соответствующего символа в строке b. Например, "abcc" лексикографически меньше "abcd", потому что первой различающейся позицией является четвертая, и 'c' меньше, чем 'd'. Пример:

Input: palindrome = "abccba"
Output: "aaccba"
Explanation: There are many ways to make "abccba" not a palindrome, such as "zbccba", "aaccba", and "abacba".
Of all the ways, "aaccba" is the lexicographically smallest.

👨‍💻 Алгоритм: 1⃣Если длина строки равна 1, верните пустую строку, так как невозможно создать непалиндромическую строку в этом случае. 2⃣Итерируйтесь по строке слева до середины строки: если символ не равен 'a', измените его на 'a' и верните строку. 3⃣Если вы прошли всю левую часть строки и все еще не получили непалиндромическую строку, это означает, что строка состоит только из 'a'. Следовательно, измените последний символ на 'b' и верните полученную строку. 😎 Решение:

class Solution {
public:
    string breakPalindrome(string palindrome) {
        int length = palindrome.size();
        
        if (length == 1) { 
            return "";
        }
        
        for (int i = 0; i < length / 2; i++) {
            if (palindrome[i] != 'a') {
                palindrome[i] = 'a';
                return palindrome;
            }
        }
        
        palindrome[length - 1] = 'b';
        return palindrome;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 206. Reverse Linked List Сложность: easy Дан односвязный список. Необходимо развернуть список и вернуть его новую голову. Пример:

Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

👨‍💻 Алгоритм: 1⃣Инициализируем два указателя: prev = nullptr — будет в итоге указывать на новую голову curr = head — начнем с текущей головы списка 2⃣Пока curr не равен nullptr: Сохраняем следующий узел: nextTemp = curr->next Меняем направление указателя: curr->next = prev Продвигаем оба указателя вперёд: prev = curr, curr = nextTemp 3⃣Когда цикл завершится, prev будет указывать на новую голову — возвращаем его. 😎 Решение:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
};

Ставь 👍 и забирай 📚 Базу знаний

🧐Слышали о контейнерах в C++, но не уверены, когда и как их правильно использовать? На открытом уроке «Контейнеры C++» 20 августа в 20:00 МСК мы разберём, как эффективно использовать стандартные и сторонние контейнеры в C++. Мы рассмотрим популярные STL-контейнеры — std::vector, std::list, std::deque, а также контейнеры-адаптеры и библиотеки сторонних разработчиков, такие как folly, boost и libcuckoo. Поймём, в каких случаях использовать каждый из них, чтобы повысить производительность и улучшить архитектуру программ. Вы получите конкретные знания, которые можно сразу применить в реальных проектах, и сможете выбирать оптимальные решения для работы с данными в C++. ⚡️Регистрируйтесь на вебинар и получите скидку на курс «C++ Developer. Professional»: https://otus.pw/v5EO/ Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576, www.otus.ru

Онлайн-магистратура с IT специальностями от Яндекса Совместно с ИТМО, МИФИ, МФТИ. Онлайн-магистратура с актуальными программами и гибким графиком обучения. Получите высокооплачиваемую IT профессию, официальный диплом и практические знания. Господдержка оплаты. Совмещение с работой! Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

Задача: 174. Dungeon Game Сложность: hard Демоны захватили принцессу и заточили её в правом нижнем углу подземелья. Подземелье состоит из m x n комнат, расположенных в виде двумерной сетки. Наш отважный рыцарь изначально находится в левом верхнем углу и должен пробиться через подземелье, чтобы спасти принцессу. У рыцаря есть начальное количество очков здоровья, представленное положительным целым числом. Если в какой-то момент его очки здоровья упадут до 0 или ниже, он немедленно умрёт. Некоторые комнаты охраняются демонами (представлены отрицательными числами), поэтому рыцарь теряет здоровье, заходя в эти комнаты; другие комнаты либо пусты (представлены как 0), либо содержат магические шары, увеличивающие здоровье рыцаря (представлены положительными числами). Чтобы как можно быстрее добраться до принцессы, рыцарь решает двигаться только вправо или вниз на каждом шаге. Верните минимальное начальное количество здоровья рыцаря, чтобы он мог спасти принцессу. Учтите, что любая комната может содержать угрозы или усиления, включая первую комнату, в которую входит рыцарь, и последнюю комнату, где заточена принцесса. Пример:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] Output: 7

👨‍💻 Алгоритм: 1⃣Определяем матрицу dp[row][col], где элемент указывает минимальное количество здоровья, необходимое рыцарю с этой позиции до конца пути. 2⃣Заполняем матрицу снизу-вверх и справа-налево, начиная с конечной ячейки, сравнивая варианты движения вправо и вниз. 3⃣Для каждой клетки берем минимальное здоровье, необходимое для движения дальше, и корректируем с учетом текущего значения подземелья. 😎 Решение:

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int rows = dungeon.size(), cols = dungeon[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols, INT_MAX));

        auto get_min_health = [&](int currCell, int nextRow, int nextCol) -> int {
            if (nextRow >= rows || nextCol >= cols) {
                return INT_MAX;
            }
            int nextCell = dp[nextRow][nextCol];
            return max(1, nextCell - currCell);
        };

        for (int row = rows - 1; row >= 0; --row) {
            for (int col = cols - 1; col >= 0; --col) {
                int currCell = dungeon[row][col];

                int right_health = get_min_health(currCell, row, col + 1);
                int down_health = get_min_health(currCell, row + 1, col);
                int next_health = min(right_health, down_health);

                int min_health;
                if (next_health != INT_MAX) {
                    min_health = next_health;
                } else {
                    min_health = currCell >= 0 ? 1 : 1 - currCell;
                }

                dp[row][col] = min_health;
            }
        }

        return dp[0][0];
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Задача: 114. Flatten Binary Tree to Linked List Сложность: medium Преобразуйте бинарное дерево в "связный список", используя тот же класс TreeNode, где right указывает на следующий элемент, а left всегда равен null. Порядок обхода должен соответствовать прямому (preorder) обходу дерева. Пример:

Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6]

👨‍💻 Алгоритм: 1⃣Рекурсивно преобразуем левое и правое поддеревья, сохраняя хвостовые узлы leftTail и rightTail. 2⃣Если у текущего узла есть левое поддерево: leftTail->right = node->right — соединяем хвост левого поддерева с началом правого. node->right = node->left — правый указатель указывает на левое поддерево. node->left = nullptr — левый указатель обнуляется. 3⃣Возвращаем в качестве хвоста либо rightTail, либо leftTail, если правого нет. 😎 Решение:

class Solution {
public:
    TreeNode* flattenTree(TreeNode* node) {
        if (node == NULL) {
            return NULL;
        }

        if (node->left == NULL && node->right == NULL) {
            return node;
        }

        TreeNode* leftTail = this->flattenTree(node->left);
        TreeNode* rightTail = this->flattenTree(node->right);

        if (leftTail != NULL) {
            leftTail->right = node->right;
            node->right = node->left;
            node->left = NULL;
        }

        return rightTail == NULL ? leftTail : rightTail;
    }

    void flatten(TreeNode* root) {
        this->flattenTree(root);
    }
};

Ставь 👍 и забирай 📚 Базу знаний

Запустите рекламу в телеграм-каналах с Яндекс Директом Перфоманс-реклама теперь в телеграм-каналах ⚡ Яндекс Директ знает, как привлечь целевую аудиторию 💰👌 Попробовать