[Leetcode] 0124. Suma máxima de rutas del árbol binario

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

A camino en un árbol binario hay una secuencia de nodos donde cada par de nodos adyacentes en la secuencia tiene una arista que los conecta. Un nodo sólo puede aparecer en la secuencia como máximo una vez. Tenga en cuenta que la ruta no necesita pasar por la raíz.

El suma de rutas de una ruta es la suma de los valores de los nodos en la ruta.

Dado que raíz de un árbol binario, retorno el máximo suma de rutas de cualquier no vacío camino.

Ejemplo 1:

Aporte: raíz = [1,2,3]
Producción: 6
Explicación: La ruta óptima es 2 -> 1 -> 3 con una suma de rutas de 2 + 1 + 3 = 6.

Ejemplo 2:

Aporte: raíz = [-10,9,20,nulo,nulo,15,7]
Producción: 42
Explicación: La ruta óptima es 15 -> 20 -> 7 con una suma de rutas de 15 + 20 + 7 = 42.

Restricciones:

El número de nodos en el árbol está en el rango [1, 3 * 10 ⁴ ].
-1000 <= Nodo.val <= 1000

Tabla de contenido

Pitón

				
					Complejidad de tiempo #: O(n) Complejidad de espacio #: O(n) de la importación de tipos Clase opcional TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right clase Solución: def maxPathSum(self, root: Optional[TreeNode]) -> int: maxPath = float('-inf') def dfs(node: Optional[TreeNode]): nonlocal maxPath si el nodo es None: devuelve 0 pathLeft = max(dfs(node.left), 0) pathRight = max(dfs(node.right), 0) maxPath = max(maxPath, pathLeft + pathRight + node.val) devuelve max(pathLeft + node.val, pathRight + node.val) dfs(root) devuelve maxPath root = TreeNode(1) raíz.izquierda = NodoArbol(2) raíz.derecha = NodoArbol(3) print(Solución().maxPathSum(raíz))

Pitón

Artículos relacionados