Travesía de orde vertical da solución LeetCode de árbore binaria

Enunciado do problema Travesía de orde vertical da árbore binaria Solución LeetCode di: Dada a raíz dunha árbore binaria, calcule a orde vertical de percorrido da árbore binaria. Para cada nodo na posición (fila, col), os seus fillos esquerdo e dereito estarán nas posicións (fila + 1, col – 1) e (fila + 1, col + 1) respectivamente. …

Le máis

Suma de raíz a números de follas Solución LeetCode

Declaración do problema Suma de raíz a números de follas A solución LeetCode di: dáselle a raíz dunha árbore binaria que só contén díxitos do 0 ao 9. Cada camiño de raíz a folla na árbore representa un número. Por exemplo, o camiño de raíz a folla 1 -> 2 -> 3 representa o número 123. Devolve a suma total de todos os números de raíz a folla. Proba…

Le máis

Solución LeetCode de Árbore Binaria Inorder Traversal

Enunciado do problema: Travesía en orde de árbore binaria Solución LeetCode Dada a raíz dunha árbore binaria, devolve o percorrido en orde dos valores dos seus nodos. Exemplo 1: Entrada: root = [1,null,2,3] Saída: [1,3,2] Exemplo 2: Entrada: root = [] Saída: [] Exemplo 3: Entrada: root = [1] Saída: [1] Restricións: o número de nodos en...

Le máis

O gráfico é bipartito? Solución LeetCode

O enunciado do problema é un gráfico bipartito Solución LeetCode: hai un gráfico non dirixido con n nós, onde cada nodo está numerado entre 0 e n – 1. Dáseche un gráfico de matriz 2D, onde graph[u] é unha matriz de nós que o nodo u está adxacente a. Máis formalmente, para cada v do gráfico[u], hai unha aresta non dirixida entre o nodo u e o nodo v. O gráfico ten...

Le máis

Deseño Engadir e buscar palabras Estrutura de datos Solución LeetCode

Declaración do problema: Deseño de palabras para engadir e buscar a estrutura de datos LeetCode Solution di: Deseña unha estrutura de datos que permita engadir novas palabras e buscar se unha cadea coincide con algunha cadea engadida anteriormente. Implementar a clase WordDictionary: WordDictionary() Inicializa o obxecto. void addWord(palabra) Engade palabra á estrutura de datos, pódese facer coincidir máis tarde. bool search(word) Devolve verdadeiro se hai...

Le máis

Aplanar a árbore binaria á lista ligada Solución LeetCode

Aplanar a árbore binaria á lista ligada Solución LeetCode di que – Dado o root dunha árbore binaria, aplana a árbore nunha "lista ligada":

  • A "lista vinculada" debería usar o mesmo TreeNode clase onde o right o punteiro fillo apunta ao seguinte nodo da lista e o left o punteiro fillo é sempre null.
  • A "lista vinculada" debe estar na mesma orde que a pre-orde travesía da árbore binaria.

 

Exemplo 1:

Aplanar a árbore binaria á lista ligada Solución LeetCodeEntrada:

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

saída:

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

Exemplo 2:

Entrada:

 root = []

saída:

 []

Exemplo 3:

Entrada:

 root = [0]

saída:

 [0]

 

ALGORITMO -

IDEA -

  • Para aplanar unha árbore binaria, primeiro atoparemos o elemento máis á dereita da subárbore esquerda e despois de obter o elemento máis á dereita vincularemos o punteiro dereito dese nodo cunha subárbore dereita dunha determinada árbore.
  • No paso 2 vincularemos o punteiro dereito do nodo raíz coa subárbore esquerda e estableceremos a subárbore esquerda como nula.
  • No paso 3 agora o noso nodo raíz é un nodo da subárbore dereita, o mesmo proceso ocorrerá con este nodo e o proceso aínda continuará ata que todas as partes da esquerda se volvan nulas.

Enfoque para aplanar a árbore binaria á lista ligada Solución Leetcode -

– Ao principio, executarei un bucle, é dicir, while(raíz != nulo) despois tomarei dúas variables e almacenarei a subárbore esquerda.

– entón comprobará o nodo máis dereito da subárbore esquerda usando while(k.left != null) e vinculará ese nodo coa subárbore dereita usando (k.right = root.right).

– A continuación, ligue o punteiro dereito do nodo raíz coa subárbore esquerda (root.right = left) e configure o punteiro esquerdo do nodo raíz como nulo (root.left=null) e actualizarase por (root = root.right) polo que agora root é correcto nodo da subárbore.

– este proceso continuará ata que todas as partes da subárbore esquerda se convertan na subárbore dereita. Polo tanto, a árbore binaria quedará aplanada.

 

Aplanar a árbore binaria á lista ligada Solución LeetCode

Aplanar a árbore binaria á lista ligada Solución LeetCode

Solución 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

Solución 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;
        }
    }
}

Complexidade temporal: O(N)

Complexidade espacial: O (1)

Como só percorremos unha vez, a complexidade do tempo será o(n).

e como non ocupamos ningún espazo extra, a complexidade do espazo será o(1) espazo extra constante.

Pregunta semellante - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm

Antepasado común máis baixo dunha solución Leetcode de árbore binaria

Declaración do problema O antepasado común máis baixo dunha árbore binaria Solución LeetCode - "Ancestro común máis baixo dunha árbore binaria" indica que dada a raíz da árbore binaria e dous nós da árbore. Necesitamos atopar o antepasado común máis baixo destes dous nós. O Común Menor…

Le máis

Pobo de punteiros á dereita en cada solución Leetcode de nodo

Declaración do problema A Poboación dos seguintes punteiros á dereita en cada nodo Solución LeetCode: "Poboando os seguintes punteiros á dereita en cada nodo" indica que, dada a raíz da árbore binaria perfecta, necesitamos encher cada seguinte punteiro do nodo ao seu seguinte nodo dereito. Se non hai seguinte...

Le máis

Translate »