Algoritmos de Java: lista enlazada en árbol binario (LeetCode) by@rakhmedovrs
108,920 lecturas

Algoritmos de Java: lista enlazada en árbol binario (LeetCode)

2022/07/09
por @rakhmedovrs 108,920 lecturas
tldt arrow
ES
Read on Terminal Reader

Demasiado Largo; Para Leer

El número de nodos en el árbol estará en el rango `[1, 2500]` para cada nodo en la lista vinculada y el árbol binario. El número máximo de nodos en un árbol binario es de 2500 nodos en una lista enlazada. La única diferencia es que TreeTree tiene un puntero adicional y eso es todo. De hecho, puede representar algunos tipos de BinaryTrees usando LinkedLists usando el mismo puntero. Necesitamos averiguar si un árbol binario dado contiene un dado. árbol binario que contiene a. lista enlazada a partir de la. cabeza. Si todos los elementos en el. vinculado. la lista de `head` corresponde a algún *camino descendente* conectado en el árbol binario; de lo contrario, devuelve False.

Company Mentioned

Mention Thumbnail
featured image - Algoritmos de Java: lista enlazada en árbol binario (LeetCode)
Ruslan Rakhmedov HackerNoon profile picture

@rakhmedovrs

Ruslan Rakhmedov

Senior Software Engineer. As a hobby I do competitive programming...

Aprender Mas
LEARN MORE ABOUT @RAKHMEDOVRS'S EXPERTISE AND PLACE ON THE INTERNET.
react to story with heart

Descripción de la tarea:

Dada la root de un árbol binario y una lista enlazada con la head como primer nodo.

Devuelve True si todos los elementos de la lista enlazada a partir de la head corresponden a algún camino descendente conectado en el árbol binario; de lo contrario, devuelve False.

En este contexto, el camino descendente significa un camino que comienza en algún nodo y va hacia abajo.

Ejemplo 1:

image

 Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3] Output: true Explanation: Nodes in blue form a subpath in the binary Tree.

Ejemplo 2:

image

 Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3] Output: true

Ejemplo 3:

 Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3] Output: false Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Restricciones:

  • El número de nodos en el árbol estará en el rango [1, 2500] .
  • El número de nodos en la lista estará en el rango [1, 100] .
  • 1 <= Node.val <= 100 para cada nodo en la lista vinculada y el árbol binario.

Razonamiento:

Parece que esta tarea nos obliga a usar al menos 2 estructuras de datos diferentes, un árbol binario y una lista vinculada. Presentemos 2 clases simples para describir piezas esenciales que forman un árbol binario y una lista enlazada.

Es posible que notes algunas similitudes entre ellos. La única diferencia es que TreeNode tiene un puntero adicional y eso es todo. De hecho, puede representar algunos tipos de BinaryTrees usando LinkedLists

Primer ejemplo de BinaryTree que puede ser representado por LinkedList

Primer ejemplo de BinaryTree que puede ser representado por LinkedList

Segundo ejemplo de BinaryTree que puede ser representado por LinkedList

Segundo ejemplo de BinaryTree que puede ser representado por LinkedList

Divirtámonos un poco y cambiemos nuestro “ángulo de visión”. Lo mismo se puede hacer con el segundo ejemplo.

Primer ejemplo girado a la izquierda

Primer ejemplo girado a la izquierda

Volvamos a nuestra tarea. Necesitamos averiguar si un árbol binario dado contiene una lista enlazada en una de sus rutas a partir de cualquier nodo. No te asustes por la definición de la tarea, es más fácil de lo que piensas.

Hablemos de la solución de fuerza bruta. Lo que podemos hacer es iterar a través de cada nodo del árbol binario y, a partir de él, iterar a través de la lista enlazada. Si iteramos a través de cada nodo en el árbol binario, será O (n) - complejidad de tiempo lineal. La iteración sobre cada nodo en la lista enlazada también será O(n). Si para cada nodo del árbol binario iteramos sobre la lista enlazada, nos dará O(n²) — complejidad de tiempo cuadrática.

¿Suena como una mala solución? Echemos un vistazo a los números proporcionados. El número máximo de nodos en un árbol binario es 2500. El número máximo de nodos en la lista enlazada es 100. 2500 * 100 = 250'000 número máximo de operaciones que tendremos que realizar para resolver el problema. Cualquier CPU moderna puede procesar hasta 10⁸ operaciones en menos de un segundo. Nuestra solución de fuerza bruta tiene 2*10⁵.

Solución:

Voy a implementar la solución utilizando un enfoque recursivo, pero también se puede resolver de forma no recursiva.

En el método isSubPath llamamos al método recursivo atravesar

En la función transversal, verificamos si el nodo raíz actual es nulo y, como resultado, devolvemos si head es o no igual a nulo. Si los valores en un nodo en el árbol binario y en un nodo en la lista enlazada son iguales, podemos intentar verificar si encontramos una coincidencia. Para hacerlo llamamos al método findPath .

De lo contrario, continuamos explorando el árbol binario yendo a los nodos izquierdo y derecho.

En el método findPath hacemos casi lo mismo que hicimos en poligonal . Si head es nulo significa que llegamos al final de la lista enlazada y devolvemos verdadero. Si root es nulo significa que exploramos todos los nodos en un árbol binario y no podemos continuar. Devolvemos falso. En todos los demás casos comprobamos la igualdad de valores en los nodos de un árbol binario y una lista enlazada. Al mismo tiempo tratamos de explorar ambos caminos desde el nodo actual del árbol binario, tratamos de ir al hijo izquierdo y al derecho. Cualquiera de las rutas disponibles será suficiente para que respondamos la pregunta principal: el árbol binario contiene todos los nodos en la lista vinculada provista.

La solución completa

Como se mencionó anteriormente, esta solución tiene una complejidad de tiempo cuadrática, pero está bien porque conocemos las restricciones exactas para la tarea. El sistema de pruebas lo demuestra.

image


HISTORIAS RELACIONADAS

L O A D I N G
. . . comments & more!
Hackernoon hq - po box 2206, edwards, colorado 81632, usa