Summa rót til blaða tölur LeetCode lausn

Vandamálsyfirlýsing Summa Rótar til blaða tölur LeetCode Lausn segir - Þú færð rót tvíundartrés sem inniheldur aðeins tölustafi frá 0 til 9. Hver slóð frá rót til blaða í trénu táknar tölu. Til dæmis táknar rót-til-blaða slóðin 1 -> 2 -> 3 töluna 123. Skilaðu heildarsummu allra rót-til-blaðatalna. Próf…

Lesa meira

Binary Tree Inorder Traversal LeetCode Lausn

Vandamálsyfirlýsing: Tvöfaldur tré í röð LeetCode lausn Með hliðsjón af rót tvöfalds trés, skilaðu óraða yfirferð hnúta þess. Dæmi 1: Inntak: rót = [1,null,2,3] Úttak: [1,3,2] Dæmi 2: Inntak: rót = [] Úttak: [] Dæmi 3: Inntak: rót = [1] Úttak: [1] Takmarkanir: Fjöldi hnúta í …

Lesa meira

Er Graph tvíhliða? LeetCode lausn

Vandamálsyfirlýsing er graf tvíhliða LeetCode lausn- Það er óstýrt línurit með n hnútum, þar sem hver hnút er númeraður á milli 0 og n – 1. Þú færð 2D fylkisgraf, þar sem graf[u] er fylki hnúta sem hnútur u. er við hlið. Meira formlega, fyrir hvert v í línuriti[u], er óstýrð brún á milli hnút u og hnút v. Grafið hefur …

Lesa meira

Hönnun Bæta við og leita að orðum Gagnauppbygging LeetCode lausn

Vandamál: Hönnun Bæta við og leita að orðum Gagnauppbygging LeetCode Lausn segir - Hannaðu gagnaskipulag sem styður við að bæta við nýjum orðum og finna hvort strengur passar við einhvern áður bættan streng. Innleiða WordDictionary flokkinn: WordDictionary() Frumstillir hlutinn. void addWord(word) Bætir orði við gagnaskipulagið, það er hægt að passa það síðar. bool leit(orð) Skilar satt ef það er…

Lesa meira

Flettu tvöfalda tré við tengda lista LeetCode lausn

Flettu tvöfalda tré við tengda lista LeetCode lausn segir að - Í ljósi þess root af tvíundartré, flettu tréð út í „tengdan lista“:

  • „Tengdi listinn“ ætti að nota það sama TreeNode bekk þar sem right barnabendill bendir á næsta hnút á listanum og left barn bendill er alltaf null.
  • „Tengdi listinn“ ætti að vera í sömu röð og a Pre-röð yfirferð af tvíundartrénu.

 

Dæmi 1:

Flettu tvöfalda tré við tengda lista LeetCode lausninntak:

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

Output:

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

Dæmi 2:

inntak:

 root = []

Output:

 []

Dæmi 3:

inntak:

 root = [0]

Output:

 [0]

 

ALGÓRITIMA -

HUGMYND -

  • Til þess að fletja út tvöfalda tré, finnum við fyrst hægra megin í vinstra undirtrénu og eftir að við höfum náð hæsta stakinu munum við tengja hægri bendilinn þess hnúts við hægri undirtré tiltekins trés.
  • Í skrefi 2 munum við tengja hægri bendilinn á rótarhnútnum við vinstri undirtréð og stilla vinstri undirtréð sem núll.
  • Í skrefi 3 er nú rótarhnúturinn okkar hægri undirtréshnútur, sama ferli mun gerast með þessum hnút og ferlið heldur áfram þar til allir vinstri hlutar verða að engu.

Aðferð til að fletja tvöfalda tré við Leetcode lausn á tengdum lista -

– Í fyrstu mun ég keyra lykkju þ.e. while(rót != null) þá mun ég taka tvær breytur og geyma vinstri undirtréð.

– mun þá athuga hvort hnúturinn sé lengst til hægri í vinstri undirtré með því að nota while(k.left != null) og mun tengja þann hnút við hægri undirtré með því að nota (k.right = root.right).

– tengdu síðan hægri bendilinn á rótarhnút við vinstri undirtré (root.right = vinstri) og stilltu vinstri bendilinn á rótarhnút sem null(root.left=null) og mun uppfæra með (rót = root.right ) þannig að nú er rót rétt undirtré hnút.

– þetta ferli mun halda áfram þar til allir vinstri undirtré hlutar verða hægri undirtré. Þess vegna mun tvíundartréð fletjast út.

 

Flettu tvöfalda tré við tengda lista LeetCode lausn

Flettu tvöfalda tré við tengda lista LeetCode lausn

Python lausn:

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

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

Tímaflæki: O(N)

Rýmisflókið: O (1)

Þar sem við höfum farið aðeins einu sinni yfir verður tímaflækjustigið o(n).

og þar sem við höfum ekki tekið neitt aukapláss verður flókið rými o(1) stöðugt aukarými.

Svipuð spurning - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Lægsti sameiginlegi forfaðir tvöfaldrar tré Leetcode lausn

Vandamálsyfirlýsing Lægsti sameiginlegi forfaðir tvíundartrés LeetCode Lausn – „Lágsti sameiginlegi forfaðir tvíundartrés“ segir að miðað við rót tvíundartrésins og tvo hnúta trésins. Við þurfum að finna lægsta sameiginlega forföður þessara tveggja hnúta. Lægsta sameign…

Lesa meira

Fylltu út næstu hægri vísbendingar í hverri hnút Leetcode lausn

Vandamálsyfirlýsing Byggða næstu hægri bendilinn í hverjum hnút LeetCode lausn - „Að fylla næstu hægri bendina í hverjum hnút“ segir að miðað við rót hins fullkomna tvíundartrés og við þurfum að fylla út hvern næsta bendi hnútsins á næsta hægri hnút sinn. Ef það er ekkert næsta…

Lesa meira

Eyða hnútum og skila Forest Leetcode lausn

Vandamálsyfirlýsing Eyða hnútum og skila skógi LeetCode lausn – „Eyða hnútum og skila skógi“ segir að miðað við rót tvíundartrésins þar sem hver hnút hefur sérstakt gildi. Okkur er líka gefið fylki, to_delete, þar sem við þurfum að eyða öllum hnútum með gildum í ...

Lesa meira

Fjöldi aðskildra eyja Leetcode lausn

Vandamálsyfirlýsing Fjöldi aðskildra eyja LeetCode Lausn – „Fjöldi aðskildra eyja“ segir að gefið anxm tvíundarfylki. Eyja er hópur 1 (sem táknar land) tengd 4-átta (lárétt eða lóðrétt). Eyja er talin vera sú sama og önnur ef og aðeins ef ein eyja …

Lesa meira

Translate »