Poäng för parentes LeetCode Solution

Problembeskrivning Poängen för Parentes LeetCode Solution säger – Givet en balanserad parentes sträng s och returnera den maximala poängen. Poängen för en balanserad parentessträng baseras på följande regler: "()" har poäng 1. AB har poäng A + B, där A och B är balanserade parentessträngar. (A) har poängen 2 * A, där A är en …

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

Avkoda sträng Leetcode-lösning

Problembeskrivning Avkodningssträngen LeetCode Lösning – "Decode String" ber dig konvertera den kodade strängen till en avkodad sträng. Kodningsregeln är k[encoded_string], där den kodade_strängen inom hakparenteserna upprepas exakt k gånger där k är ett positivt heltal. Exempel: Ingång: s = ”3[a]2[bc]” Utgång: ”aaabcbc” …

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ägg till Two Numbers II Leetcode-lösning

Problembeskrivning Add Two Numbers II LeetCode-lösningen – "Add Two Numbers II" anger att två icke-tomma länkade listor representerar två icke-negativa heltal där den mest signifikanta siffran kommer först och varje nod innehåller exakt en siffra. Vi måste lägga till de två talen och returnera summan som ...

Läs mer

Dagliga temperaturer Leetcode-lösning

Problembeskrivning Dagliga temperaturer Leetcode Lösning: anger att givet en uppsättning heltal temperaturer representerar de dagliga temperaturerna, returnera ett matrissvar så att svar[i] är antalet dagar du måste vänta efter den i:te dagen för att få en varmare temperatur. Om det inte finns någon framtida dag för vilken detta är möjligt, behåll svar[i] == 0 istället. …

Läs mer

Minsta borttagning för att göra giltiga parenteser LeetCode-lösning

Problembeskrivning Minsta borttagning för att göra giltiga parenteser LeetCode Lösning – Du får en sträng med '(', ')' och engelska bokstäver med gemener. Din uppgift är att ta bort det minsta antalet parenteser ( '(' eller ')', i alla positioner ) så att den resulterande parentessträngen är ...

Läs mer

Infångning av regnvatten Leetcode-lösning

Problembeskrivning The Trapping Rain Water LeetCode Solution – "Fånga regnvatten" säger att givet en rad höjder som representerar en höjdkarta där bredden på varje stapel är 1. Vi måste hitta mängden vatten som fångas efter regn. Exempel: Ingång: höjd = [0,1,0,2,1,0,1,3,2,1,2,1] Utdata: 6 Förklaring: Kontrollera …

Läs mer

Giltiga parenteser Leetcode-lösning

Problembeskrivning De giltiga parenteserna LeetCode Solution – "Giltig parentes" anger att du får en sträng som bara innehåller tecknen '(', ')', '{', '}', '[' och ']'. Vi måste avgöra om inmatningssträngen är en giltig sträng eller inte. En sträng sägs vara en giltig sträng om öppna parenteser måste stängas ...

Läs mer

Maximal Frequency Stack Leetcode-lösning

Problembeskrivning Maximum Frequency Stack LeetCode Solution – "Maximum Frequency Stack" ber dig att designa en frekvensstack där varje gång vi poppar ett element från stacken, ska det returnera det vanligaste elementet som finns i stacken. Implementera FreqStack-klassen: FreqStack() konstruerar en tom frekvensstack. void push(int val) trycker ...

Läs mer

Translate »