Резултат от скоби LeetCode Solution

Постановка на проблема Резултатът на Parenthesis LeetCode Solution казва – Даден е балансиран низ в скоби и връщане на максималния резултат. Резултатът от балансиран низ със скоби се основава на следните правила: “()” има резултат 1. AB има резултат A + B, където A и B са балансирани низове в скоби. (A) има резултат 2 * A, където A е ...

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

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

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

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

Решение за декодиране на стринг Leetcode

Постановка на проблема Решението на Decode String LeetCode – „Decode String“ ви моли да конвертирате кодирания низ в декодиран низ. Правилото за кодиране е k[encoded_string], където encoded_string в квадратните скоби се повтаря точно k пъти, където k е цяло положително число. Пример: Вход: s = ”3[a]2[bc]” Изход: “aaabcbc” …

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

Изравняване на двоичното дърво до свързан списък Решение на 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

Добавете две числа II Leetcode Solution

Постановка на проблема Решението за добавяне на две числа II LeetCode – „Добавяне на две числа II“ заявява, че два непразни свързани списъка представляват две неотрицателни цели числа, където най-значимата цифра е първа и всеки възел съдържа точно една цифра. Трябва да съберем двете числа и да върнем сумата като...

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

Ежедневни температури Leetcode Solution

Постановка на проблема Ежедневните температури Решение на Leetcode: заявява, че даден масив от цели числа температури представлява дневните температури, връща отговор на масив, така че answer[i] е броят на дните, които трябва да изчакате след i-тия ден, за да получите по-топла температура. Ако няма бъдещ ден, за който това е възможно, запазете answer[i] == 0 вместо това. …

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

Минимално премахване, за да направите валидни скоби LeetCode Solution

Пояснение на проблема Минималното премахване, за да направите валидни скоби Решение на LeetCode – Получавате низ от '(', ')' и малки английски символи. Вашата задача е да премахнете минималния брой скоби ( '(' или ')', във всяка позиция), така че резултантният низ със скоби да е ...

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

Решение за улавяне на дъждовна вода Leetcode

Постановка на проблема Решението LeetCode за улавяне на дъждовна вода – „Улавяне на дъждовна вода“ посочва, че даден масив от височини представлява карта на надморската височина, където ширината на всяка лента е 1. Трябва да намерим количеството вода, уловена след дъжд. Пример: Вход: височина = [0,1,0,2,1,0,1,3,2,1,2,1] Изход: 6 Обяснение: Проверете ...

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

Валидни скоби Leetcode Solution

Постановка на проблема. Решението за валидни скоби LeetCode – „Валидни скоби“ гласи, че ви е даден низ, съдържащ само знаците '(', ')', '{', '}', '[' и ']'. Трябва да определим дали входният низ е валиден низ или не. За даден низ се казва, че е валиден низ, ако отворените скоби трябва да бъдат затворени...

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

Лийткодово решение за стека на максималната честота

Постановка на проблема Решението на LeetCode за стека с максимална честота – „Стак с максимална честота“ ви моли да проектирате честотен стек, в който всеки път, когато извадим елемент от стека, той трябва да връща най-често срещания елемент, присъстващ в стека. Реализирайте класа FreqStack: FreqStack() изгражда празен честотен стек. void push(int val) бута ...

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

Translate »