İkili Ağacı Əlaqəli Siyahıya Düzləşdirin LeetCode Həll deyir ki, - nəzərə alınmaqla root ikili ağacın, ağacı "əlaqəli siyahı" halına salın:

• "Əlaqələndirilmiş siyahı" eyni istifadə etməlidir TreeNode sinif harada right uşaq göstərici siyahıda növbəti node və left uşaq göstərici həmişə null.
• "Əlaqələndirilmiş siyahı" a ilə eyni sırada olmalıdır əvvəlcədən sifariş xain ikili ağacdan.

 

Misal 1:

Input:

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

Çıxış:

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

Misal 2:

Input:

 root = []

Çıxış:

 []

Misal 3:

Input:

 root = [0]

Çıxış:

 [0]

 

ALQORİTM -

İDEA -

• İkili ağacı düzəltmək üçün əvvəlcə sol alt ağacın ən sağ elementini tapacağıq və ən sağdakı elementi əldə etdikdən sonra həmin düyünün sağ göstəricisini verilmiş ağacın sağ alt ağacı ilə əlaqələndirəcəyik.
• 2-ci addımda biz kök qovşağının sağ göstəricisini sol-alt ağac ilə əlaqələndirəcəyik və sol-alt ağacı null olaraq təyin edəcəyik.
• 3-cü addımda indi bizim kök qovşağımız sağ-alt ağac qovşağıdır. Eyni proses bu qovşaqda baş verəcək və bütün sol hissələr sıfır olana qədər proses davam edəcək.

İkili Ağacı Əlaqəli Siyahıya Düzləşdirmək üçün Yanaşma - Leetcode Həll

– Əvvəlcə bir dövrə işlədəcəm, yəni while(root != null) sonra iki dəyişən götürüb sol-alt ağacı saxlayacağam.

– sonra while(k.left != null) istifadə edərək sol alt ağacın ən sağdakı qovşağını yoxlayacaq və (k.right = root.right) istifadə edərək həmin qovşağı sağ alt ağacla əlaqələndirəcək.

– sonra kök nodunun sağ göstəricisini sol alt ağac ilə əlaqələndirin (root.right = left) və kök nodun sol göstəricisini null (root.left=null) olaraq təyin edin və (root.left=null) ilə yenilənəcək, buna görə də indi kök sağdır. alt ağac qovşağı.

– bu proses bütün sol-alt ağac hissələri sağ alt ağaca çevrilənə qədər davam edəcək. Beləliklə, ikili ağac yastılaşacaq.

 

Python Həlli:

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 Həlli:

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

Zaman mürəkkəbliyi: O(N)

Kosmik Mürəkkəblik: O (1)

Yalnız bir dəfə keçdiyimiz üçün zaman mürəkkəbliyi o(n) olacaqdır.

və biz heç bir əlavə yer tutmadığımıza görə, kosmik mürəkkəblik o(1) daimi əlavə yer olacaqdır.

Oxşar Sual - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm