Vertikální procházení pořadí binárního stromu řešení LeetCode

Prohlášení o problému Vertikální procházení binárního stromu Řešení LeetCode říká – Vzhledem ke kořenu binárního stromu vypočítejte vertikální procházení binárního stromu. Pro každý uzel na pozici (řádek, sloupec) budou jeho levé a pravé potomky na pozicích (řádek + 1, sloupec – 1) a (řádek + 1, sloupec + 1). …

Dozvědět se více

Řešení LeetCode součet odmocnin k listům

Problémové prohlášení Odmocnina součtu k číslům listu Řešení LeetCode říká – Je vám dán kořen binárního stromu obsahující pouze číslice od 0 do 9. Každá cesta od kořene k listu ve stromu představuje číslo. Například cesta od kořene k listu 1 -> 2 -> 3 představuje číslo 123. Vrátí celkový součet všech čísel odmocninového listu. Test …

Dozvědět se více

Binární strom Inorder Traversal řešení LeetCode

Příkaz problému: Binary Tree Inorder Traversal LeetCode solution Daný kořen binárního stromu vraťte inorder traversal hodnot jeho uzlů. Příklad 1: Vstup: root = [1,null,2,3] Výstup: [1,3,2] Příklad 2: Vstup: root = [] Výstup: [] Příklad 3: Vstup: root = [1] Výstup: [1] Omezení: Počet uzlů v …

Dozvědět se více

Srovnat binární strom do propojeného seznamu řešení LeetCode

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:

Srovnat binární strom do propojeného seznamu řešení LeetCodeVstup:

 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.

 

Srovnat binární strom do propojeného seznamu řešení LeetCode

Srovnat binární strom do propojeného seznamu řešení LeetCode

Ř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

Nejnižší společný předek řešení Leetcode Binary Tree

Problémové prohlášení Nejnižší společný předek binárního stromu Řešení LeetCode – „Nejnižší společný předek binárního stromu“ uvádí, že daný kořen binárního stromu a dva uzly stromu. Musíme najít nejnižšího společného předka těchto dvou uzlů. Nejnižší běžné…

Dozvědět se více

Vyplnění dalších pravých ukazatelů v každém řešení Leetcode uzlu

Prohlášení o problému Vyplnění dalších pravých ukazatelů v každém uzlu Řešení LeetCode – „Vyplnění dalších pravých ukazatelů v každém uzlu“ uvádí, že daný kořen dokonalého binárního stromu a každý další ukazatel uzlu musíme naplnit na jeho další pravý uzel. Pokud není další…

Dozvědět se více

Odstraňte uzly a vraťte řešení Forest Leetcode

Prohlášení o problému Řešení LeetCode Delete Nodes and Return Forest – „Delete Nodes and Return Forest“ uvádí, že vzhledem ke kořeni binárního stromu má každý uzel odlišnou hodnotu. Máme také pole to_delete, kde potřebujeme smazat všechny uzly s hodnotami obsaženými v …

Dozvědět se více

Obnovte řešení Leetcode Binary Search Tree

Prohlášení o problému The Recover Binary Search Tree LeetCode Solution – “Recover Binary Search Tree” uvádí, že daný kořen binárního vyhledávacího stromu, kde jsou omylem prohozeny hodnoty právě dvou uzlů. Potřebujeme obnovit strom, aniž bychom změnili jeho strukturu. Příklad: Vstup: root = [1,3,null,null,2] Výstup: [3,1,null,null,2] …

Dozvědět se více

Řešení Symmetric Tree Leetcode

Problémové prohlášení Symetrický strom Řešení LeetCode – „Symetrický strom“ uvádí, že daným kořenem binárního stromu a my potřebujeme zkontrolovat, zda daný binární strom je zrcadlem sebe sama (symetrický kolem svého středu) nebo ne? Pokud Ano, musíme vrátit true, jinak false. Příklad:…

Dozvědět se více

Počítejte dobré uzly v řešení Leetcode v binárním stromu

Prohlášení o problému V tomto problému je binární strom uveden s kořenem. Uzel X ve stromu se jmenuje dobrý, pokud na cestě od kořene k X nejsou žádné uzly s hodnotou větší než X. Musíme vrátit počet dobrých uzlů v…

Dozvědět se více

Translate »