Žingsnis po žingsnio instrukcijos nuo dvejetainio medžio mazgo iki kito „LeetCode“ sprendimo

Problemos pareiškimas: nuoseklios instrukcijos nuo dvejetainio medžio mazgo iki kito „LeetCode“ sprendimo – jums suteikiama dvejetainio medžio, turinčio n mazgų, šaknis. Kiekvienam mazgui unikaliai priskiriama reikšmė nuo 1 iki n. Taip pat gausite sveikąjį startValue, nurodantį pradinio mazgo s reikšmę, ir kitą sveikąjį skaičių destValue, nurodantį paskirties vietą...

Skaityti daugiau

Dvejetainio medžio „LeetCode“ sprendimo vertikalioji tvarka

Problemos teiginys Dvejetainio medžio vertikalios eilės važiavimas LeetCode Sprendimas sako: Atsižvelgdami į dvejetainio medžio šaknį, apskaičiuokite dvejetainio medžio vertikalios eilės eigą. Kiekvieno mazgo padėtyje (eilutė, stulpelis) jo kairioji ir dešinioji antroji dalis bus atitinkamai (eilutė + 1, stulpelis – 1) ir (eilė + 1, stulpelis + 1). …

Skaityti daugiau

„LeetCode“ sprendimas

Problemos teiginys Suma nuo šaknies iki lapų skaičių LeetCode Sprendimas sako – Jums duota dvejetainio medžio šaknis, kurioje yra tik skaitmenys nuo 0 iki 9. Kiekvienas medžio kelias nuo šaknies iki lapo reiškia skaičių. Pavyzdžiui, kelias nuo šaknies iki lapo 1 -> 2 -> 3 reiškia skaičių 123. Pateikite bendrą visų skaičių nuo šaknies iki lapo sumą. Išbandyti…

Skaityti daugiau

Binary Tree Inorder Traversal LeetCode sprendimas

Problemos teiginys: Binary Tree Inorder Traversal LeetCode sprendimas Atsižvelgiant į dvejetainio medžio šaknį, grąžinkite jo mazgų reikšmių eilės eilutę. 1 pavyzdys: Įvestis: root = [1,null,2,3] Išvestis: [1,3,2] 2 pavyzdys: Įvestis: šaknis = [] Išvestis: [] 3 pavyzdys: Įvestis: root = [1] Išvestis: [1] Apribojimai: mazgų skaičius…

Skaityti daugiau

Išlyginkite dvejetainį medį į susieto sąrašo „LeetCode“ sprendimą

Išlyginkite dvejetainį medį į susieto sąrašo „LeetCode“ sprendimą sako, kad – Atsižvelgiant į root iš dvejetainio medžio, išlyginkite medį į susietą sąrašą:

  • „Susietame sąraše“ turėtų būti naudojamas tas pats TreeNode klasėje, kur right antrinis žymeklis nurodo kitą sąrašo mazgą ir left vaiko rodyklė visada yra null.
  • „Susietas sąrašas“ turėtų būti tokia pat tvarka kaip a iš anksto užsisakyti perėjimas dvejetainio medžio.

 

Pavyzdys 1:

Išlyginkite dvejetainį medį į susieto sąrašo „LeetCode“ sprendimąĮvestis:

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

Rezultatas:

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

Pavyzdys 2:

Įvestis:

 root = []

Rezultatas:

 []

Pavyzdys 3:

Įvestis:

 root = [0]

Rezultatas:

 [0]

 

ALGORITMAS -

IDĖJA –

  • Norėdami išlyginti dvejetainį medį, pirmiausia rasime dešinįjį kairiojo pomedžio elementą, o gavę dešinįjį elementą susiesime to mazgo dešinįjį rodyklę su duoto medžio dešiniuoju pomedžiu.
  • 2 veiksme mes susiesime dešinįjį šakninio mazgo rodyklę su kairiuoju pomedžiu ir nustatysime kairįjį pomedį kaip nulį.
  • 3 veiksme dabar mūsų šakninis mazgas yra dešiniojo pomedžio mazgas. Tas pats procesas vyks ir su šiuo mazgu, ir procesas tęsis tol, kol visos kairiosios dalys taps nulinės.

Dvejetainio medžio išlyginimo į susieto sąrašo „Leetcode“ sprendimas –

– Iš pradžių paleisiu kilpą, ty while(root != null), tada paimsiu du kintamuosius ir išsaugosiu kairįjį pomedį.

– tada patikrins, ar yra dešiniausias kairiojo pomedžio mazgas, naudojant while(k.left != null), ir susies tą mazgą su dešiniuoju pomedžiu naudojant (k.right = root.right).

– tada susiekite dešinįjį šakninio mazgo žymeklį su kairiuoju pomedžiu (root.right = left) ir nustatykite kairįjį šakninio mazgo žymeklį kaip nulį (root.left=null) ir atnaujins (root = root.right), taigi dabar šaknis yra dešinė pomedžio mazgas.

– šis procesas tęsis tol, kol visos kairiosios pomedžio dalys taps dešiniuoju pomedžiu. Taigi dvejetainis medis bus suplotas.

 

Išlyginkite dvejetainį medį į susieto sąrašo „LeetCode“ sprendimą

Išlyginkite dvejetainį medį į susieto sąrašo „LeetCode“ sprendimą

Python sprendimas:

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 sprendimas:

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;
        }
    }
}

Laiko sudėtingumas: O(N)

Erdvės sudėtingumas: O (1)

Kadangi perėjome tik vieną kartą, laiko sudėtingumas bus o(n).

ir kadangi mes neužėmėme jokios papildomos vietos, erdvės sudėtingumas bus o(1) nuolatinė papildoma erdvė.

Panašus klausimas - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Žemiausias bendras dvejetainio medžio protėvis Leetcode sprendimas

Problemos teiginys Žemiausias bendras dvejetainio medžio protėvis LeetCode sprendimas – „Žemiausias bendras dvejetainio medžio protėvis“ teigia, kad atsižvelgiant į dvejetainio medžio šaknį ir du medžio mazgus. Turime rasti žemiausią bendrą šių dviejų mazgų protėvį. Žemiausias bendras…

Skaityti daugiau

Kitų dešiniųjų rodyklių užpildymas kiekviename mazgo „Leetcode“ sprendime

Problemos pareiškimas Kitų dešiniųjų rodyklių užpildymas kiekviename mazge „LeetCode“ sprendimas – „Kiekvieno mazgo kito dešiniojo rodyklės užpildymas“ teigia, kad atsižvelgiant į tobulo dvejetainio medžio šaknį ir kiekvieną kitą mazgo rodyklę turime užpildyti į kitą dešinįjį mazgą. Jei nebus kito…

Skaityti daugiau

Ištrinkite mazgus ir grąžinkite Forest Leetcode sprendimą

Problemos pareiškimas Trinti mazgus ir grąžinti mišką „LeetCode“ sprendimas – „Ištrinti mazgus ir grąžinti mišką“ nurodo, kad, atsižvelgiant į dvejetainio medžio šaknį, kiekvienas mazgas turi skirtingą reikšmę. Mums taip pat suteikiamas masyvas to_delete, kuriame turime ištrinti visus mazgus, kurių reikšmės yra…

Skaityti daugiau

Atkurkite dvejetainio paieškos medžio „Leetcode“ sprendimą

Problemos pareiškimas Dvejetainės paieškos medžio atkūrimo LeetCode sprendimas – „Atkurti dvejetainį paieškos medį“ teigia, kad atsižvelgiant į dvejetainio paieškos medžio šaknį, kur per klaidą sukeistos lygiai dviejų mazgų reikšmės. Turime atkurti medį nekeičiant jo struktūros. Pavyzdys: Įvestis: root = [1,3,null,null,2] Išvestis: [3,1,null,null,2] …

Skaityti daugiau

Translate »