Traversamentu di l'Ordine Verticale di l'Arburu Binariu Soluzione LeetCode

Problem Statement Ordine Verticale Traversal of Binary Tree LeetCode Solution dice - Data a radica di un arbulu binariu, calculate l'ordine verticale traversal di l'arbulu binariu. Per ogni node in pusizioni (fila, col), i so figlioli left and right seranu in pusizioni (fila + 1, col - 1) è (fila + 1, col + 1) rispettivamente. …

Read more

Sum Root to Leaf Numbers Soluzione LeetCode

Problem Statement Sum Root to Leaf Numbers LeetCode Solution dice - Vi sò datu a radica di un arbulu binariu chì cuntene numeri da 0 à 9 solu. Ogni percorsu da a radica à a foglia in l'arbulu rapprisenta un numeru. Per esempiu, u percorsu da a radica à a foglia 1 -> 2 -> 3 rapprisenta u numeru 123. Ritorna a summa tutale di tutti i numeri di a radica à a foglia. Test…

Read more

Arbulu Binariu Inorder Traversal Soluzione LeetCode

Problem Statement: Binary Tree Inorder Traversal Soluzione LeetCode Data a radica di un arbulu binariu, restituite a traversa in ordine di i valori di i so nodi. Esempiu 1: Input: root = [1,null,2,3] Output: [1,3,2] Esempiu 2: Input: root = [] Output: [] Esempiu 3: Input: root = [1] Output: [1] Limitazioni: U numeru di nodi in ...

Read more

Hè Graph Bipartite? Soluzione LeetCode

Problem Statement Is Graph Bipartite LeetCode Solution- Ci hè un grafu senza direzzione cù n nodi, induve ogni nodu hè numeratu trà 0 è n - 1. Vi hè datu un gràficu array 2D, induve graph[u] hè un array di nodi chì u node u. hè adiacente à. Più formalmente, per ogni v in graph[u], c'è un bordo non diretto tra i nodi u e i nodi v. Il grafico ha...

Read more

Design Add and Search Words Data Structure Soluzione LeetCode

Problem Statement: Design Add and Search Words Data Structure LeetCode Solution dice - Progettate una struttura di dati chì sustene l'aghjunzione di novi parole è truvà se una stringa currisponde à qualsiasi stringa aghjunta previamente. Implementa a classe WordDictionary: WordDictionary() Inizializza l'ughjettu. void addWord (parola) Aghjunghje a parolla à a struttura di dati, pò esse cumminata dopu. ricerca bool (parola) Ritorna vera se ci hè ...

Read more

Appiattà l'Arburu Binariu à a Lista Ligata Soluzione LeetCode

Appiattà l'Arburu Binariu à a Lista Ligata Soluzione LeetCode dice chì – Data u root di un arbre binariu, appiattite l'arburu in una "lista ligata":

  • A "lista ligata" deve aduprà u listessu TreeNode classe induve u right puntatore di u zitellu punta à u prossimu node in a lista è u left puntatore zitellu hè sempre null.
  • A "lista ligata" deve esse in u listessu ordine cum'è a pre-ordine traversu di l'arburu binariu.

 

Esemplariu 1:

Appiattà l'Arburu Binariu à a Lista Ligata Soluzione LeetCodeInput:

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

Output:

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

Esemplariu 2:

Input:

 root = []

Output:

 []

Esemplariu 3:

Input:

 root = [0]

Output:

 [0]

 

ALGORITMU -

IDEA -

  • Per appiattà un arbulu binariu, truvemu prima l'elementu rightmost di u subtree left è dopu avè ottenutu l'elementu rightmost, ligheremu u punter right-pointer di quellu node cù un subtree right di un arbulu datu.
  • In u passu 2 ligaremu u punteru dirittu di u node radicali cù u subtree left è stabilisce u subtree left cum'è null.
  • In u passu 3 avà u nostru node radicali hè un nodu subtree right u stessu prucessu accadrà cù questu node è u prucessu continuarà sempre finu à chì tutte e parte manca diventanu nulle.

Approcciu per Flatten Binary Tree to Linked List Soluzione Leetcode -

– À u principiu, eseguiraghju un loop, vale à dì while(root != null) dopu piglià duie variàbili è almacenà u subtree left.

- dopu verificarà u nodu più à destra di u subtree left usendu while (k.left != null) è ligà quellu node cù u subtree right usendu (k.right = root.right).

- poi ligà u puntatore right di u nodu radicale cù u subtree left (root.right = left) è stabilisce u puntatore left di u node root cum'è null (root.left = null) è aghjurnerà da (root = root.right) cusì avà a radica hè ghjustu. node subtree.

- stu prucessu hà da cuntinuà finu à chì tutte e parti di u subtree di manca diventanu subtree right. Dunque, l'arbulu binariu sarà appiattitu.

 

Appiattà l'Arburu Binariu à a Lista Ligata Soluzione LeetCode

Appiattà l'Arburu Binariu à a Lista Ligata Soluzione LeetCode

Soluzione 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

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

A cumplessità di u tempu: O(N)

Cumplessità Spaziale: O (1)

Cumu avemu traversatu una sola volta, a cumplessità di u tempu serà o (n).

è cum'è ùn avemu micca pigliatu un spaziu extra, a cumplessità di u spaziu serà o (1) spaziu extra constantu.

Domanda simile - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

U più bassu Antenatu cumuni di una Soluzione Leetcode di l'Arburu Binariu

Dichjarazione di u Prublemu L'Ancestor Common Lowest di un Arbulu Binariu Soluzione LeetCode - "Ancestor Common Lowest of a Binary Tree" dice chì datu a radica di l'arbulu binariu è dui nodi di l'arbulu. Avemu bisognu di truvà l'antenatu cumuni più bassu di sti dui nodi. U più bassu cumuni…

Read more

Populing Next Pointers Right in ogni Node Soluzione Leetcode

Problem Statement U Populing Next Right Pointers in Each Node Soluzione LeetCode - "Populating Next Right Pointers in Each Node" dichjara chì datu a radica di l'arbulu binariu perfettu è avemu bisognu di populate ogni puntatore prossimu di u node à u so prossimu node right. S'ellu ùn ci hè u prossimu…

Read more

Translate »