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:

Ingå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.

 

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