Выраўнаваць двайковае дрэва ў звязаны спіс LeetCode Solution кажа, што – Улічваючы root двайковага дрэва, зраўняйце дрэва ў «звязаны спіс»:

• «Звязаны спіс» павінен выкарыстоўваць тое ж самае TreeNode клас, дзе right даччыны паказальнік паказвае на наступны вузел у спісе і left даччыны паказальнік заўсёды null.
• «Звязаны спіс» павінен быць у тым жа парадку, што і a Папярэдні заказ абход бінарнага дрэва.

 

Прыклад 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