Descripción de la tarea: Dada la de un árbol binario y una lista enlazada con la como primer nodo. root head Devuelve True si todos los elementos de la lista enlazada a partir de la corresponden a algún conectado en el árbol binario; de lo contrario, devuelve False. head camino descendente 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] para cada nodo en la lista vinculada y el árbol binario. 1 <= Node.val <= 100 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 llamamos al método recursivo isSubPath 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 hacemos casi lo mismo que hicimos en . 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. findPath poligonal 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.

Different

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Coding

2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Coding

Este audio es producido en el idioma original de la historia!

Demasiado Largo; Para Leer

Let Your Engineers & PMs focus on Product. Apply for $50K Credits!

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

Demasiado Largo; Para Leer

Company Mentioned

@rakhmedovrs

HISTORIAS RELACIONADAS