Puntuación da solución LeetCode entre parénteses

Enunciado do problema A puntuación de Paréntese LeetCode Solution di: Dada unha cadea de parénteses equilibrada s e devolve a puntuación máxima. A puntuación dunha cadea de parénteses equilibrada baséase nas seguintes regras: "()" ten unha puntuación 1. AB ten unha puntuación A + B, onde A e B son cadeas de parénteses equilibradas. (A) ten puntuación 2 * A, onde A é un...

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

Solución Leetcode de Decode String

Declaración do problema A solución LeetCode Decode String: "Decode String" pídelle que converta a cadea codificada nunha cadea descodificada. A regra de codificación é k[cadea_codificada], onde a cadea_codificada dentro dos corchetes repítese exactamente k veces onde k é un número enteiro positivo. Exemplo: Entrada: s = ”3[a]2[bc]” Saída: “aaabcbc”…

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

Engadir dous números II Solución Leetcode

Enunciado do problema A solución LeetCode de Engadir dous números II: "Engadir dous números II" indica que dúas listas enlazadas non baleiras representan dous enteiros non negativos onde o díxito máis significativo é primeiro e cada nodo contén exactamente un díxito. Necesitamos sumar os dous números e devolver a suma como...

Le máis

Solución Leetcode de temperaturas diarias

Declaración do problema As temperaturas diarias Solución Leetcode: indica que, dada unha matriz de enteiros, as temperaturas representan as temperaturas diarias, devolve unha resposta matricial de xeito que a resposta[i] é o número de días que ten que esperar despois do iésimo día para obter unha temperatura máis cálida. Se non hai ningún día futuro para o que isto sexa posible, mantén answer[i] == 0 no seu lugar. …

Le máis

Eliminación mínima para facer parénteses válidos Solución LeetCode

Declaración do problema A eliminación mínima para facer parénteses válidos Solución LeetCode: dáselle unha cadea s de '(', ')' e caracteres ingleses en minúscula. A súa tarefa é eliminar o número mínimo de parénteses ('(' ou ')', en calquera posición) para que a cadea de parénteses resultante sexa...

Le máis

Solución Leetcode para atrapar augas pluviais

Declaración do problema A solución de LeetCode Trapping Rain Water: "Trapping Rain Water" indica que dada unha serie de alturas que representa un mapa de elevación onde o ancho de cada barra é 1. Necesitamos atopar a cantidade de auga atrapada despois da choiva. Exemplo: Entrada: altura = [0,1,0,2,1,0,1,3,2,1,2,1] Saída: 6 Explicación: Comprobar...

Le máis

Parénteses válidas Solución Leetcode

Declaración do problema A solución LeetCode de parénteses válidos: "Parénteses válidos" indica que se lle da unha cadea que contén só os caracteres '(', ')', '{', '}', '[' e ']'. Necesitamos determinar se a cadea de entrada é unha cadea válida ou non. Dise que unha cadea é unha cadea válida se os corchetes abertos deben estar pechados...

Le máis

Solución Leetcode de pila de frecuencia máxima

Declaración do problema A pila de frecuencia máxima Solución LeetCode: "Pila de frecuencia máxima" pídelle que deseña unha pila de frecuencias na que sempre que saquemos un elemento da pila, debería devolver o elemento máis frecuente presente na pila. Implementar a clase FreqStack: FreqStack() constrúe unha pila de frecuencias baleira. void push(int val) pushs...

Le máis

Translate »