Srovnat binární strom do propojeného seznamu řešení LeetCode říká, že – Vzhledem k root binárního stromu, srovnejte strom do „propojeného seznamu“:

• „Propojený seznam“ by měl používat totéž TreeNode třída, kde right podřízený ukazatel ukazuje na další uzel v seznamu a left dětský ukazatel je vždy null.
• „Propojený seznam“ by měl být ve stejném pořadí jako a pre-order traverz binárního stromu.

 

Příklad 1:

Vstup:

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

Výstup:

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

Příklad 2:

Vstup:

 root = []

Výstup:

 []

Příklad 3:

Vstup:

 root = [0]

Výstup:

 [0]

 

ALGORITHM –

IDEA -

• Abychom binární strom srovnali, nejprve najdeme prvek levého podstromu nejvíce vpravo a poté, co získáme prvek nejvíce vpravo, spojíme pravý ukazatel tohoto uzlu s pravým podstromem daného stromu.
• V kroku 2 propojíme pravý ukazatel kořenového uzlu s levým podstromem a levý podstrom nastavíme jako null.
• V kroku 3 je nyní náš kořenový uzel uzlem pravého podstromu stejný proces se stane s tímto uzlem a proces bude stále pokračovat, dokud se všechny levé části nestanou nulovými.

Přístup pro Flatten Binary Tree to Linked List Leetcode Solution –

– Nejprve spustím smyčku, tj. while(root != null), poté vezmu dvě proměnné a uložím levý podstrom.

– poté zkontroluje kontrolu pravého uzlu levého podstromu pomocí while(k.left != null) a propojí tento uzel s pravým podstromem pomocí (k.right = root.right).

– poté propojte pravý ukazatel kořenového uzlu s levým podstromem (root.right = left) a nastavte levý ukazatel kořenového uzlu jako null (root.left=null) a aktualizuje se o ( root = root.right ), takže nyní je root pravý uzel podstromu.

– tento proces bude pokračovat, dokud se všechny části levého podstromu nestanou pravým podstromem. Binární strom se tedy zplošťuje.

 

Řešení 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 řešení:

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

Časová složitost: O(N)

Složitost prostoru: O (1)

Protože jsme prošli pouze jednou, časová složitost bude o(n).

a protože jsme nevzali žádný prostor navíc, složitost prostoru bude o (1) konstantní prostor navíc.

Podobná otázka - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm