Преброяване на подострови LeetCode решение

Изявление на проблема Брой под острови LeetCode Solution казва, че grid1 и grid2 съдържат само 0 (представляващи вода) и 1 (представляващи земя). Островът означава група от 1, свързани 4 посоки. Остров в grid2 се счита за подостров, ако има остров в grid1, който съдържа всички клетки, които правят...

Прочети повече

Обхождане на вертикален ред на двоично дърво LeetCode решение

Изявление на проблема Преминаване по вертикален ред на двоично дърво LeetCode Solution казва – Като се има предвид коренът на двоично дърво, изчислете обхождането по вертикален ред на двоичното дърво. За всеки възел на позиция (ред, колона), неговите леви и десни деца ще бъдат съответно на позиции (ред + 1, колона – 1) и (ред + 1, колона + 1). …

Прочети повече

Сума корен към числа на листа LeetCode Solution

Постановка на проблема Сума корен на листови числа. Решението на LeetCode казва – Даден е коренът на двоично дърво, съдържащо само цифри от 0 до 9. Всеки път от корен до лист в дървото представлява число. Например пътят от корен до лист 1 -> 2 -> 3 представлява числото 123. Върнете общата сума от всички числа от корен до лист. Тест …

Прочети повече

Решение за преход на двоично дърво в ред LeetCode

Постановка на проблема: Двоично дърво Inorder Traversal LeetCode решение Като се има предвид коренът на двоично дърво, върнете обхода в ред на стойностите на неговите възли. Пример 1: Вход: root = [1,null,2,3] Изход: [1,3,2] Пример 2: Вход: root = [] Изход: [] Пример 3: Вход: root = [1] Изход: [1] Ограничения: Броят на възлите в…

Прочети повече

Двустранна ли е графиката? Решение на LeetCode

Постановката на проблема е Graph Bipartite LeetCode Solution- Има ненасочена графика с n възела, където всеки възел е номериран между 0 и n – 1. Получавате 2D масивна графика, където graph[u] е масив от възли, които възел u е в съседство с. По-формално, за всеки v в graph[u], има ненасочен ръб между възел u и възел v. Графата има ...

Прочети повече

Дизайн Добавяне и търсене на думи Структура на данни LeetCode Solution

Постановка на проблема: Проектиране на структура на данни за добавяне и търсене на думи LeetCode Solution казва – Проектирайте структура от данни, която поддържа добавяне на нови думи и намиране дали даден низ съвпада с някой по-рано добавен низ. Реализирайте класа WordDictionary: WordDictionary() Инициализира обекта. void addWord(word) Добавя дума към структурата на данните, тя може да бъде съпоставена по-късно. bool search(word) Връща true, ако има...

Прочети повече

Изравняване на двоичното дърво до свързан списък Решение на LeetCode

Изравняване на двоичното дърво до свързан списък Решение на LeetCode казва, че – Като се има предвид root на двоично дърво, изравнете дървото в „свързан списък“:

  • „Свързаният списък“ трябва да използва същото TreeNode клас, където right дъщерният указател сочи към следващия възел в списъка и left детски указател е винаги null.
  • „Свързаният списък“ трябва да бъде в същия ред като a предварителна поръчка обръщане на двоичното дърво.

 

Пример 1:

Изравняване на двоичното дърво до свързан списък Решение на LeetCodeВход:

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

Изход:

 [1,null,2,null,3,null,4,null,5,null,6]

Пример 2:

Вход:

 root = []

Изход:

 []

Пример 3:

Вход:

 root = [0]

Изход:

 [0]

 

АЛГОРИТЪМ –

ИДЕЯ –

  • За да изравним едно двоично дърво, първо ще намерим най-десния елемент от лявото поддърво и след като получим най-десния елемент, ще свържем десния указател на този възел с дясното поддърво на дадено дърво.
  • В стъпка 2 ще свържем десния показалец на коренния възел с лявото поддърво и ще зададем лявото поддърво като нула.
  • В стъпка 3 сега нашият основен възел е възел от дясно поддърво. Същият процес ще се случи с този възел и процесът ще продължи, докато всички леви части станат нулеви.

Подход за изравняване на двоично дърво към свързан списък Leetcode Решение –

– Първо ще стартирам цикъл, т.е. while(root != null), след това ще взема две променливи и ще съхраня лявото поддърво.

– след това ще провери проверката за най-десния възел на лявото поддърво, като използва while(k.left != null) и ще свърже този възел с дясното поддърво, използвайки (k.right = root.right).

– след това свържете десния указател на коренния възел с лявото поддърво(root.right = left) и задайте левия указател на коренния възел като null(root.left=null) и ще се актуализира чрез ( root = root.right ), така че сега root е прав възел на поддърво.

– този процес ще продължи, докато всички части на лявото поддърво не станат дясно поддърво. Следователно, двоичното дърво ще бъде сплескано.

 

Изравняване на двоичното дърво до свързан списък Решение на LeetCode

Изравняване на двоичното дърво до свързан списък Решение на LeetCode

Решение на Python:

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        while(root):
            
            if root.left:
                
                k = root.left
                temp = root.left
            
            
                while(k.right):
                    k = k.right
            
                k.right = root.right
            
                root.right = temp
            
                root.left = None
            
            root = root.right

Java решение:

class Solution {
    public void flatten(TreeNode root) {       
        while (root != null) {
            if (root.left != null) {
                TreeNode k = root.left;
                TreeNode temp = root.left;
                while (k.right != null) k = k.right;
                k.right = root.right;
                root.right = temp;
                root.left = null;
            }
            root = root.right;
        }
    }
}

Времева сложност: O(N)

Космическа сложност: O (1)

Тъй като сме преминали само веднъж, времевата сложност ще бъде o(n).

и тъй като не сме заели допълнително пространство, сложността на пространството ще бъде o(1) постоянно допълнително пространство.

Подобен въпрос - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Диаметър на N-Ary Tree LeetCode Solution

Постановка на проблема: Диаметърът на N-арното дърво Решение на LeetCode – Като се има предвид корен на N-арно дърво, трябва да изчислите дължината на диаметъра на дървото. Диаметърът на N-арно дърво е дължината на най-дългия път между всеки два възела в дървото. Този път може или не...

Прочети повече

Най-нисък общ предшественик на решението на бинарно дърво Leetcode

Постановка на проблема Най-нисък общ предшественик на двоично дърво LeetCode Solution – „Най-нисък общ предшественик на двоично дърво“ заявява, че се има предвид коренът на двоичното дърво и два възела на дървото. Трябва да намерим най-ниския общ предшественик на тези два възела. Най-ниското често срещано…

Прочети повече

Попълване на следващия десен указател във всеки възел Leetcode решение

Постановка на проблема Попълването на следващия десен указател във всеки възел Решение на LeetCode – „Попълване на следващия десен указател във всеки възел“ посочва, че като се има предвид коренът на перфектното двоично дърво и трябва да попълним всеки следващ указател на възела до следващия му десен възел. Ако няма следващо…

Прочети повече

Translate »