Rrafshoni Pemën Binare në Zgjidhjen LeetCode të Listës së Lidhur thotë se – Duke pasur parasysh root të një peme binare, rrafshoni pemën në një "listë të lidhur":

• "Lista e lidhur" duhet të përdorë të njëjtën gjë TreeNode klasa ku right treguesi i fëmijës tregon në nyjen tjetër në listë dhe left treguesi i fëmijës është gjithmonë null.
• "Lista e lidhur" duhet të jetë në të njëjtin rend si a para-qëllim përshkimi të pemës binare.

 

1 Shembull:

input:

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

output:

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

2 Shembull:

input:

 root = []

output:

 []

3 Shembull:

input:

 root = [0]

output:

 [0]

 

ALGORITMI -

IDE -

• Për të rrafshuar një pemë binare, fillimisht do të gjejmë elementin më të djathtë të nënpemës së majtë dhe pasi të kemi marrë elementin më të djathtë, do të lidhim treguesin e djathtë të asaj nyje me një nënpemë të djathtë të një peme të caktuar.
• Në hapin 2 ne do të lidhim treguesin e djathtë të nyjës rrënjë me nënpemën e majtë dhe do ta vendosim nënpemën e majtë si null.
• Në hapin 3 tani nyja jonë rrënjë është një nyje e nënpemës së djathtë i njëjti proces do të ndodhë me këtë nyje dhe procesi do të vazhdojë akoma derisa të gjitha pjesët e majta të bëhen të pavlefshme.

Qasje për rrafshimin e pemës binare me zgjidhjen e kodit Leetcode të listës së lidhur -

– Në fillim, do të ekzekutoj një lak, dmth while(root != null) më pas do të marr dy variabla dhe do të ruaj nënpemën e majtë.

– pastaj do të kontrollojë kontrollin për nyjen më të djathtë të nënpemës së majtë duke përdorur while(k.left != null) dhe do ta lidhë atë nyje me nënpemën e djathtë duke përdorur (k.right = root.right).

– më pas lidhni treguesin e djathtë të nyjës rrënjë me nënpemën e majtë (root.djathtas = majtas) dhe vendosni treguesin e majtë të nyjes rrënjë si null (root.left=null) dhe do të përditësohet me (rrënjë = rrënjë.djathtas) kështu që tani rrënja është e drejtë nyja e nënpemës.

– ky proces do të vazhdojë derisa të gjitha pjesët e nënpemës së majtë të bëhen nënpema e djathtë. Prandaj, pema binare do të rrafshohet.

 

Zgjidhja e Python:

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

Zgjidhja Java:

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

Kompleksiteti kohor: O(N)

Kompleksiteti i hapësirës: O (1)

Meqë kemi përshkuar vetëm një herë, kompleksiteti kohor do të jetë o(n).

dhe meqenëse nuk kemi zënë hapësirë ​​shtesë, kompleksiteti i hapësirës do të jetë o(1) hapësirë ​​shtesë konstante.

Pyetje e ngjashme - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm