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

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:

 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:

 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.

https://gist.github.com/RakhmedovRS/94bf17787d3873117997e9d3fa0a23e1

https://gist.github.com/RakhmedovRS/3c97726e4aa77734d817947131b7696a

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

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

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

https://gist.github.com/RakhmedovRS/4fcfe3c046099ab3a1362854b36ec3e5

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.

https://gist.github.com/RakhmedovRS/bbe2bc542f73aea6d7ec035fa5313de3

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.

https://gist.github.com/RakhmedovRS/e9a1695b8e14c2de165fa36489a4b454

La solución completa

https://gist.github.com/RakhmedovRS/db8111d9d89a0ba2d910f5ef37036290

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.