Contar buenos nodos en un árbol binario
Guía detallada e implementación de Python para el problema 'Contar nodos buenos en árbol binario'.
1. aprender
El problema 'Contar buenos nodos en un árbol binario' es un desafío clave en la sección Árboles.
Esta implementación se centra en la lógica de nivel medio en Python.
Priorizamos la precisión técnica y la legibilidad del código en las soluciones que brindamos.
2. Real-World Applications
3. Visual Intuition
Visualizando el flujo lógico para contar buenos nodos en un árbol binario.
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
Lea atentamente el enunciado del problema de Contar buenos nodos en un árbol binario.
2. Formulate brute force
Redacte una solución iterativa simple.
3. Identify inefficiency
Busque cálculos redundantes.
4. Optimize search path
Utilice hash o clasificación para acelerar el proceso.
5. Final Implementation
Limpiar el código para los estándares de producción.
Declaración del problema
Dada una raíz de árbol binario, un nodo X en el árbol se considera bueno si en el camino desde la raíz hasta X no hay nodos con un valor mayor que X.
Devuelve el número de nodos buenos en el árbol binario.
El árbol se representa como una lista de orden de niveles. Implementar una función goodNodes(root: list) -> int.
- •The number of nodes in the binary tree is in the range [1, 100000]
- •-10000 <= Node.val <= 10000
Ejemplos
[3,1,4,3,None,1,5]
4
Root 3 is always good. Node 4 (3<=4, good). Node 3 under node 1 (3<=3, good). Node 5 (3<=4<=5, good). Node 1 is not good (3>1). Node 1 under 4 is not good (4>1). Total: 4 good nodes.
[3,3,None,4,2]
3
Root 3 is good. Node 3 (left child, 3<=3, good). Node 4 (3<=3<=4, good). Node 2 is not good (3>2). Total: 3.
[1]
1
The root is always a good node.
Need a Hint?
Edge Cases to Watch
- Estructuras de entrada vacías
- Entradas de un solo elemento
- Grandes límites numéricos
¿Listo para resolver?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
Ideas y variaciones de la entrevista
Desglose del análisis de complejidad
Por qué el tiempo: Directly evaluates all possibilities.
Por qué el espacio: Uses standard local memory.
Por qué el tiempo: Optimized paths reduce total operations.
Por qué el espacio: May trade memory for speed.
Código Python de solución optimizada
Código Python de solución optimizada
def good_nodes_opt(root):
if isinstance(root, list):
r = build_tree(root)
return good_nodes_opt_helper(r)
return good_nodes_opt_helper(root)
def good_nodes_opt_helper(root: TreeNode) -> int:
def dfs(node, max_val):
if not node:
return 0
res = 1 if node.val >= max_val else 0
max_val = max(max_val, node.val)
res += dfs(node.left, max_val)
res += dfs(node.right, max_val)
return res
return dfs(root, float('-inf'))Código de fuerza bruta (spoiler guardado)
Código de fuerza bruta (spoiler guardado)
def good_nodes_brute(root):
if isinstance(root, list):
r = build_tree(root)
return good_nodes_brute_helper(r)
return good_nodes_brute_helper(root)
def good_nodes_brute_helper(root: TreeNode) -> int:
def dfs(node, path):
if not node: return 0
is_good = 1 if all(x <= node.val for x in path) else 0
path.append(node.val)
left = dfs(node.left, path)
right = dfs(node.right, path)
path.pop()
return is_good + left + right
return dfs(root, [])Algorithm Pattern Checklist
When dealing with Trees data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
Key Revision Notes
Se aplican las propiedades del problema de árboles estándar.
Preguntas relacionadas
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
Recursos recomendados de Python
Amplíe sus conocimientos con tutoriales interactivos relacionados, hojas de trucos y comparaciones de códigos.
Prueba/excepto de Python y manejo de errores
Evite que sus scripts de Python fallen. Aprenda a intentar, excepto, finalmente bloquear y cómo generar excepciones personalizadas correctamente.
Cómo invertir una cadena en Python
Aprenda a invertir una cadena en Python usando el corte, la función invertida() y la concatenación de bucles con ejemplos de código visual.
Hoja de trucos sobre métodos de cadenas de Python
Una guía de referencia completa para la manipulación de cadenas de Python. Domine el formateo, la búsqueda, la división, el reemplazo y la verificación de las propiedades de las cadenas.
Python vs JavaScript: ¿Qué lenguaje de programación es mejor?
Una comparación completa entre Python y JavaScript. Explore las diferencias de sintaxis, el rendimiento, los casos de uso (backend frente a frontend) y ejemplos de codificación.