Екілік ағашты байланыстырылған тізімге тегістеңіз LeetCode шешімі былай дейді – ескере отырып root екілік ағаштың, ағашты «байланыстырылған тізімге» тегістеңіз:

• «Байланыстырылған тізім» бірдей қолданылуы керек TreeNode сынып қайда right еншілес көрсеткіш тізімдегі келесі түйінді көрсетеді және left бала көрсеткіші әрқашан null.
• «Байланыстырылған тізім» келесімен бірдей тәртіпте болуы керек алдын ала берілетін тапсырыс көлденең екілік ағаштан.

 

Мысал 1:

Кіру:

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

Шығару:

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

Мысал 2:

Кіру:

 root = []

Шығару:

 []

Мысал 3:

Кіру:

 root = [0]

Шығару:

 [0]

 

АЛГОРИТМ –

ИДЕЯ –

• Екілік ағашты тегістеу үшін алдымен сол жақ ішкі ағаштың оң жақ элементін табамыз және ең оң жақ элементті алғаннан кейін сол түйіннің оң жақ көрсеткішін берілген ағаштың оң жақ ішкі ағашымен байланыстырамыз.
• 2-қадамда біз түбірлік түйіннің оң жақ көрсеткішін сол жақ ішкі ағашпен байланыстырамыз және сол жақ ішкі ағашты нөл ретінде орнатамыз.
• 3-қадамда енді біздің түбір түйініміз оң жақтағы ішкі ағаш түйіні. Дәл сол процесс осы түйінмен орындалады және барлық сол жақ бөліктер нөлге айналғанша процесс жалғаса береді.

Екілік ағашты байланыстырылған тізімге тегістеу әдісі Leetcode шешімі –

– Алдымен циклды іске қосамын, яғни while(root != null) содан кейін екі айнымалыны алып, сол жақтағы ішкі ағашты сақтаймын.

– содан кейін while(k.left != null) көмегімен сол жақтағы ішкі ағаштың ең оң жақ түйінін тексереді және сол түйінді оң жақтағы ішкі ағашпен байланыстырады (k.right = root.right).

– содан кейін түбірлік түйіннің оң жақ көрсеткішін сол ішкі ағашпен байланыстырыңыз (root.right = left) және түбірлік түйіннің сол жақ көрсеткішін null (root.left=null) етіп орнатыңыз және ( root = root.right ) арқылы жаңартылады, сондықтан енді түбір дұрыс. ішкі ағаш түйіні.

– бұл процесс барлық сол жақтағы ішкі ағаш бөліктері оң жақ ішкі ағаш болғанша жалғасады. Осылайша, екілік ағаш тегістеледі.

 

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

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

Уақыт күрделілігі: O(N)

Ғарыштың күрделілігі: O (1)

Біз тек бір рет жүріп өткендіктен, уақыт күрделілігі o(n) болады.

және біз ешқандай қосымша орын алмағандықтан, кеңістіктің күрделілігі o(1) тұрақты қосымша кеңістік болады.

Ұқсас сұрақ – https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm