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

Je graf bipartitní? Řešení LeetCode

Problémové prohlášení je graf Bipartite LeetCode Řešení- Existuje neorientovaný graf s n uzly, kde každý uzel je očíslován mezi 0 a n – 1. Dostanete 2D graf pole, kde graph[u] je pole uzlů, které uzel u sousedí s. Formálněji, pro každé v v grafu[u] existuje mezi uzlem u a uzlem v neorientovaná hrana. Graf má …

Dozvědět se více

Návrh datové struktury pro přidávání a vyhledávání slov Řešení LeetCode

Prohlášení o problému: Navrhněte datovou strukturu přidat a vyhledat slova Řešení LeetCode říká – Navrhněte datovou strukturu, která podporuje přidávání nových slov a zjišťování, zda se řetězec shoduje s dříve přidaným řetězcem. Implementujte třídu WordDictionary: WordDictionary() Inicializuje objekt. void addWord(word) Přidá slovo do datové struktury, lze jej později spárovat. bool search(word) Vrátí true, pokud…

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

Translate »