Екілік ағаштың ретімен өтуі LeetCode шешімі

Мәселе туралы мәлімдеме: Екілік ағаштың ретімен өтуі LeetCode шешімі Екілік ағаштың түбірін ескере отырып, оның түйіндерінің мәндерінің ретімен өтуін қайтарыңыз. 1-мысал: Енгізу: root = [1,null,2,3] Шығару: [1,3,2] 2-мысал: Кіріс: root = [] Шығу: [] 3-мысал: Кіріс: root = [1] Шығыс: [1] Шектеулер: ... ішіндегі түйіндер саны

Ары қарай оқу

Минималды жол сомасының Leetcode шешімі

Мәселенің мәлімдемесі Минималды жол сомасы LeetCode шешімі – «Ең аз жол сомасы» берілген anxm торы теріс емес бүтін сандардан тұратынын және жол бойындағы барлық сандардың қосындысын азайтатын жоғарғы солдан төмен оңға қарай жолды табу керек екенін айтады. . Біз тек қозғала аламыз ...

Ары қарай оқу

Баспалдақпен өрмелеудің минималды құны LeetCode шешімі

Мәселе туралы мәлімдеме Баспалдақпен көтерілудің минималды құны LeetCode шешімі – бүтін массив құны берілген, мұнда құны [i] – баспалдақтағы i-ші қадамның құны. Құнды төлегеннен кейін сіз бір немесе екі сатыға көтеріле аласыз. Сіз 0 индексі бар қадамнан немесе ... бар қадамнан бастай аласыз.

Ары қарай оқу

Екілік ағашты байланыстырылған тізімге тегістеңіз LeetCode шешімі

Екілік ағашты байланыстырылған тізімге тегістеңіз LeetCode шешімі былай дейді – ескере отырып root екілік ағаштың, ағашты «байланыстырылған тізімге» тегістеңіз:

  • «Байланыстырылған тізім» бірдей қолданылуы керек TreeNode сынып қайда right еншілес көрсеткіш тізімдегі келесі түйінді көрсетеді және left бала көрсеткіші әрқашан null.
  • «Байланыстырылған тізім» келесімен бірдей тәртіпте болуы керек алдын ала берілетін тапсырыс көлденең екілік ағаштан.

 

Мысал 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 ) арқылы жаңартылады, сондықтан енді түбір дұрыс. ішкі ағаш түйіні.

– бұл процесс барлық сол жақтағы ішкі ағаш бөліктері оң жақ ішкі ағаш болғанша жалғасады. Осылайша, екілік ағаш тегістеледі.

 

Екілік ағашты байланыстырылған тізімге тегістеңіз 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

Жою GetRandom O(1) Leetcode шешімін кірістіріңіз

Мәселе туралы мәлімдеме Insert Delete GetRandom O(1) LeetCode шешімі – “Insert Delete GetRandom O(1)” осы төрт функцияны O(1) уақыт күрделілігінде орындауды сұрайды. insert(val): вальді рандомизацияланған жиынға енгізіңіз және элемент бастапқыда жиында жоқ болса, шын мәнін қайтарыңыз. Ол жалған мәнін қайтарғанда…

Ары қарай оқу

LRU Cache Leetcode шешімі

Мәселе туралы мәлімдеме LRU кэшінің LeetCode шешімі – «LRU кэші» ең аз пайдаланылған (LRU) кэшінен кейінгі деректер құрылымын жобалауды сұрайды. Бізге келесі функциялары бар LRUCache сыныбын енгізу қажет: LRUCache(int сыйымдылығы): LRU кэшін инициализациялайды. оң өлшемді сыйымдылықпен. int get (int пернесі): мәнді қайтару ...

Ары қарай оқу

Жарамды жақшаларды жасау үшін ең аз жою LeetCode шешімі

Мәселе туралы мәлімдеме Жарамды жақшаларды жасау үшін ең аз жою LeetCode шешімі – Сізге '(', ')' және кіші әріпті ағылшын таңбаларынан тұратын s жолы беріледі. Сіздің міндетіңіз - жақшалардың ең аз санын (кез келген орындарда '(' немесе ')') алып тастау, осылайша алынған жақшалар жолы ...

Ары қарай оқу

Қайталанатын таңбаларсыз ең ұзын ішкі жол Leetcode шешімі

Мәселе мәлімдемесі Қайталанатын таңбаларсыз ең ұзын ішкі жол LeetCode шешімі – s жолының берілгенін айтады. Біз таңбаларды қайталамай ең ұзын ішкі жолды табуымыз керек. Мысал: Енгізу: s = ”abcabcbb” Шығару: 3 Түсіндірме: Қайталанбайтын таңбаларсыз ең ұзын ішкі жолдың ұзындығы 3. Жол: “abc”. Енгізу: s = “bbbbb”…

Ары қарай оқу

Fibonacci саны LeetCode шешімі

Мәселе мәлімдемесі Фибоначчи саны LeetCode шешімі – «Фибоначчи саны» әдетте F(n) деп белгіленген Фибоначчи сандары Фибоначчи тізбегі деп аталатын тізбекті құрайтынын, әрбір сан 0 және 1-ден басталатын алдыңғы екі санның қосындысы болатынын айтады. Яғни, F(0) = 0, F(1) = 1 F(n) = F(n – 1) + F(n …)

Ары қарай оқу

Жаңбыр суын ұстау Leetcode шешімі

Мәселе туралы мәлімдеме Жаңбыр суын ұстау LeetCode шешімі – «Жаңбыр суын ұстау» әр жолақтың ені 1 болатын биіктік картасын көрсететін биіктіктер жиымы берілгенін айтады. Жаңбырдан кейін қалған судың мөлшерін табу керек. Мысал: Енгізу: биіктік = [0,1,0,2,1,0,1,3,2,1,2,1] Шығару: 6 Түсіндірме: Тексеру …

Ары қарай оқу

Translate »