Steg-för-steg-anvisningar från en binär trädnod till en annan LeetCode-lösning

Problembeskrivning: Steg-för-steg-anvisningar från en binär trädnod till en annan LeetCode-lösning – Du får roten till ett binärt träd med n noder. Varje nod är unikt tilldelad ett värde från 1 till n. Du får också ett heltal startValue som representerar värdet på startnoden s, och ett annat heltal destValue som representerar värdet på destinationen ...

Läs mer

Vertikal ordningsgenomgång av binärt träd LeetCode-lösning

Problembeskrivning Vertikal ordningsgenomgång av binärt träd LeetCode Lösning säger – Givet roten till ett binärt träd, beräkna den vertikala ordningens genomgång av det binära trädet. För varje nod vid position (rad, kol), kommer dess vänstra och högra barn att vara på positioner (rad + 1, kol – 1) respektive (rad + 1, kol + 1). …

Läs mer

Summa rot till blad nummer LeetCode Solution

Problembeskrivning Summa rot till blad nummer LeetCode Lösning säger – Du får roten till ett binärt träd som endast innehåller siffror från 0 till 9. Varje rot-till-blad-bana i trädet representerar ett nummer. Till exempel representerar rot-till-blad-banan 1 -> 2 -> 3 talet 123. Returnera den totala summan av alla rot-till-blad-tal. Testa…

Läs mer

Binary Tree Inorder Traversal LeetCode Solution

Problembeskrivning: Binärt träd Inorder Traversal LeetCode-lösning Givet roten till ett binärt träd, returnera inorder-traversal av dess nodvärden. Exempel 1: Ingång: root = [1,null,2,3] Utdata: [1,3,2] Exempel 2: Ingång: root = [] Utdata: [] Exempel 3: Ingång: root = [1] Utdata: [1] Restriktioner: Antalet noder i …

Läs mer

Platta ut binärt träd till länkad lista LeetCode-lösning

Platta ut binärt träd till länkad lista LeetCode-lösning säger att – Med tanke på root av ett binärt träd, platta till trädet till en "länkad lista":

  • Den "länkade listan" bör använda samma TreeNode klass där right barnpekaren pekar på nästa nod i listan och left barnpekaren är alltid null.
  • Den "länkade listan" ska vara i samma ordning som en pre-order korsning av det binära trädet.

 

Exempel 1:

Platta ut binärt träd till länkad lista LeetCode-lösningIngång:

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

Produktion:

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

Exempel 2:

Ingång:

 root = []

Produktion:

 []

Exempel 3:

Ingång:

 root = [0]

Produktion:

 [0]

 

ALGORITM –

IDÉ –

  • För att platta till ett binärt träd, kommer vi först att hitta elementet längst till höger i det vänstra underträdet och efter att vi fått elementet längst till höger kommer vi att länka den högra pekaren för den noden med ett höger underträd i ett givet träd.
  • I steg 2 kommer vi att länka den högra pekaren för rotnoden med det vänstra underträdet och ställa in det vänstra underträdet som null.
  • I steg 3 är nu vår rotnod en nod med höger underträd, samma process kommer att ske med denna nod och processen kommer fortfarande att fortsätta tills alla de vänstra delarna blir noll.

Tillvägagångssätt för att platta ut binärt träd till länkad lista Leetcode-lösning –

– Först kommer jag att köra en loop, dvs while(root != null) och sedan ta två variabler och lagra det vänstra underträdet.

– kommer då att kontrollera efter noden längst till höger i det vänstra underträdet genom att använda while(k.left != null) och länka den noden med det högra underträdet med (k.right = root.right).

– länka sedan högerpekaren för rotnoden med vänster underträd (root.right = vänster) och ställ in rotnodens vänstra pekare som null(root.left=null) och kommer att uppdateras med ( root = root.right ) så nu är roten höger underträdsnod.

– denna process kommer att fortsätta tills alla delar av vänster underträd blir högra underträd. Därför kommer det binära trädet att bli tillplattat.

 

Platta ut binärt träd till länkad lista LeetCode-lösning

Platta ut binärt träd till länkad lista LeetCode-lösning

Python lösning:

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-lösning:

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

Tidskomplexitet: O(N)

Rymdkomplexitet: O (1)

Eftersom vi bara har korsat en gång kommer tidskomplexiteten att vara o(n).

och eftersom vi inte har tagit något extra utrymme kommer rymdkomplexiteten att vara o(1) konstant extra utrymme.

Liknande fråga - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Lägsta gemensamma förfader till ett binärt träd Leetcode-lösning

Problembeskrivning Den lägsta gemensamma förfadern till ett binärt träd LeetCode Solution – "Lägsta gemensamma förfadern till ett binärt träd" anger att givet roten till det binära trädet och två noder i trädet. Vi måste hitta den lägsta gemensamma förfadern av dessa två noder. Den lägsta vanliga …

Läs mer

Fylla på nästa högerpekare i varje nod Leetcode-lösning

Problembeskrivning Fylla nästa högerpekare i varje nod LeetCode Lösning – "Populera nästa högerpekare i varje nod" säger att givet roten till det perfekta binära trädet och vi måste fylla varje nästa pekare i noden till dess nästa högra nod. Om det inte finns någon nästa...

Läs mer

Ta bort noder och returnera Forest Leetcode-lösning

Problembeskrivning Ta bort noder och returnera skog LeetCode Lösning – "Ta bort noder och returnera skog" anger att givet roten av det binära trädet där varje nod har ett distinkt värde. Vi får också en array, to_delete, där vi måste ta bort alla noder med värden som finns i ...

Läs mer

Återställ Binary Search Tree Leetcode Solution

Problembeskrivning Återställ binärt sökträd LeetCode Solution – "Återställ binärt sökträd" säger att givet roten till det binära sökträdet, där värdena för exakt två noder byts om av misstag. Vi måste återställa trädet utan att ändra dess struktur. Exempel: Indata: root = [1,3,null,null,2] Output: [3,1,null,null,2] …

Läs mer

Translate »