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!

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

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Cómo mejorar su flujo de trabajo 10 veces: 17 aplicaciones esenciales

Nómadas digitales escuchen: lo que necesitan saber sobre la nueva visa DTV de Tailandia

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Cómo mejorar su flujo de trabajo 10 veces: 17 aplicaciones esenciales

Nómadas digitales escuchen: lo que necesitan saber sobre la nueva visa DTV de Tailandia

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps