Diámetro, altura y árboles balanceados
Calcule el diámetro y la altura de un árbol en una sola pasada DFS mediante un helper que devuelva ambos valores y compruebe si el árbol está equilibrado por altura.
Diámetro, altura y árboles balanceados es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Altura de un árbol binario
La altura (o profundidad máxima) de un árbol binario es la longitud del camino más largo desde la raíz hasta cualquier hoja. Se calcula de forma recursiva: la altura de cualquier nodo es 1 + max(height(left), height(right)), con un caso base de 0 para los nodos null. Este cálculo postorden es fundamental: la altura es la base del diámetro, la comprobación del equilibrio y las rotaciones de árboles AVL.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height(root):
if not root:
return 0
return 1 + max(height(root.left), height(root.right))
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
print(height(root)) # 4Diámetro: el camino más largo
El diámetro de un árbol binario es la longitud del camino más largo entre dos nodos cualesquiera (el camino puede pasar o no por la raíz). La longitud del camino se mide en aristas. Para cualquier nodo, el diámetro que pasa por ese nodo es igual a height(left) + height(right). El diámetro general es el mayor de estos valores entre todos los nodos del árbol.
def diameter_of_binary_tree(root):
max_diameter = [0] # use list to allow closure mutation
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Diameter through this node
max_diameter[0] = max(max_diameter[0], left_h + right_h)
return 1 + max(left_h, right_h) # height for parent
dfs(root)
return max_diameter[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_of_binary_tree(root)) # 3Una sola pasada DFS para calcular el diámetro
El enfoque ingenuo llama a height() en cada nodo, lo que produce O(n²) en un árbol equilibrado. La solución óptima calcula la altura y actualiza el diámetro en una sola pasada DFS. La idea clave es que la función recursiva dfs() cumple dos propósitos simultáneamente: devuelve la altura al padre y, como efecto secundario, actualiza un diámetro máximo global. Este patrón postorden de doble propósito aparece en muchos problemas de árboles.
# O(n^2) NAIVE: recomputes height for every node
def diameter_naive(root):
if not root:
return 0
through_root = height(root.left) + height(root.right)
in_left = diameter_naive(root.left)
in_right = diameter_naive(root.right)
return max(through_root, in_left, in_right)
# O(n) OPTIMAL: single DFS pass (shown in previous scene)
# The naive version is O(n^2) because height() is O(n)
# and it is called for every node.
print('Naive: O(n^2) | Optimal single-pass: O(n)')Comprobación de árbol binario equilibrado
Un árbol binario está equilibrado en altura si las alturas de los subárboles izquierdo y derecho de cada nodo difieren como máximo en uno. El enfoque de fuerza bruta llama a height() en cada nodo, lo que produce O(n²). El enfoque óptimo utiliza el mismo truco de una sola pasada: devuelve -1 como valor centinela para indicar «no equilibrado» y lo propaga hacia arriba, deteniéndose pronto en cuanto encuentra un nodo desequilibrado.
def is_balanced(root):
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1:
return -1 # propagate early exit
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1 # unbalanced here
return 1 + max(left, right) # height if balanced
return check(root) != -1
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5) # too deep on left
print(is_balanced(root)) # FalsePatrón del valor de retorno centinela
Devolver un valor centinela (-1 para indicar que no está equilibrado, o una tupla especial) es un patrón común cuando un auxiliar DFS necesita comunicar dos tipos de información: el resultado calculado y si se infringió una restricción. En lugar de lanzar excepciones o utilizar indicadores globales, codifique el error en el tipo de retorno. Este enfoque es claro, evita el estado global y se combina de forma natural con otros auxiliares recursivos.
# General pattern: return (is_valid, computed_value)
def balanced_height(node):
if not node:
return True, 0
left_ok, left_h = balanced_height(node.left)
if not left_ok:
return False, 0 # short-circuit
right_ok, right_h = balanced_height(node.right)
if not right_ok:
return False, 0
balanced = abs(left_h - right_h) <= 1
return balanced, 1 + max(left_h, right_h)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ok, h = balanced_height(root)
print(ok, h) # True 2Diámetro en términos de nodos y aristas
Preste atención al enunciado del problema: LeetCode #543 mide el diámetro en aristas, mientras que algunos problemas lo miden en nodos. Si necesita contar nodos, el diámetro que pasa por un nodo es height(left) + height(right) + 1 (sume 1 por el propio nodo). Si necesita contar aristas, omita el +1. Aclare siempre este detalle con el entrevistador antes de programar.
def diameter_in_nodes(root):
max_path = [0]
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Path through this node in NODE count
nodes_through = left_h + right_h + 1
max_path[0] = max(max_path[0], nodes_through)
return 1 + max(left_h, right_h)
dfs(root)
return max_path[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_in_nodes(root)) # 4 nodes: 4-2-1-3 or 5-2-1-3Suma de un camino: cualquier camino de raíz a hoja
El problema de la suma de un camino pregunta si la suma de algún camino de raíz a hoja es igual a un valor objetivo. Utilice DFS y reste el valor del nodo actual al objetivo a medida que desciende. En una hoja, compruebe si el objetivo restante es igual al valor de la hoja. Este es un DFS en preorden en el que se pasa la suma restante como parámetro, un ejemplo clásico de recursión de arriba abajo.
def has_path_sum(root, target):
if not root:
return False
# Leaf node: check if we've exactly hit the target
if not root.left and not root.right:
return root.val == target
remaining = target - root.val
return (has_path_sum(root.left, remaining) or
has_path_sum(root.right, remaining))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5+4+11+2=22Suma máxima de un camino (variante difícil)
La suma máxima de un camino (LeetCode #124) es considerablemente más difícil: el camino puede comenzar y terminar en cualquier nodo, no solo en una ruta de raíz a hoja, y los valores pueden ser negativos. En cada nodo, considere cuatro opciones: solo el nodo, nodo + rama izquierda, nodo + rama derecha o nodo + ambas ramas. Solo las tres primeras pueden extenderse hacia el padre; la cuarta es una candidata terminal para el máximo global.
def max_path_sum(root):
max_sum = [float('-inf')]
def gain(node):
if not node:
return 0
# Only take positive contributions
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
# Best path through this node (can't go both ways upward)
max_sum[0] = max(max_sum[0], node.val + left + right)
# Return the best single-branch gain for parent
return node.val + max(left, right)
gain(root)
return max_sum[0]
root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_path_sum(root)) # 42: 15+20+7Árboles AVL y autoequilibrado
Un árbol AVL es un BST que mantiene la propiedad de equilibrio en altura mediante rotaciones después de las operaciones de inserción y eliminación. Cada nodo almacena un factor de equilibrio (altura derecha - altura izquierda), que debe mantenerse en {-1, 0, 1}. Cuando se produce una infracción, una rotación simple o doble restaura el equilibrio en tiempo O(1), mantiene la altura general en O(log n) y garantiza que todas las operaciones sean O(log n).
# Balance factor = height(right) - height(left)
# AVL invariant: balance factor in {-1, 0, 1} for every node
# Four violation types and their fixes:
# LL (left-heavy left child): single right rotation
# RR (right-heavy right child): single left rotation
# LR (right-heavy left child): left rotate child, then right rotate root
# RL (left-heavy right child): right rotate child, then left rotate root
# Knowing this is enough for interviews; you rarely implement
# full AVL in an interview but must discuss the concept.
print('AVL maintains O(log n) height via rotations')Comprobación de árbol simétrico
Un árbol binario es simétrico si es una imagen especular de sí mismo. Compruébelo de forma recursiva: el árbol es simétrico si, para cada par de nodos correspondientes a ambos lados del eje, sus valores son iguales y sus subárboles son imágenes especulares. Defina un auxiliar is_mirror(left, right) que compruebe lo siguiente: ambos son null (correcto), uno es null (incorrecto), los valores son iguales y los subárboles internos y externos son imágenes especulares.
def is_symmetric(root):
def is_mirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
return is_mirror(root.left, root.right)
sym = TreeNode(1)
sym.left = TreeNode(2)
sym.right = TreeNode(2)
sym.left.left = TreeNode(3)
sym.right.right = TreeNode(3)
print(is_symmetric(sym)) # True
nosym = TreeNode(1)
nosym.left = TreeNode(2)
nosym.right = TreeNode(2)
nosym.left.right = TreeNode(3)
print(is_symmetric(nosym)) # FalseCómo combinar los conceptos de altura y diámetro
El patrón de recorrido posorden en una sola pasada, en el que una función auxiliar devuelve simultáneamente la altura y actualiza un resultado global, se puede reutilizar en muchos problemas: diámetro, suma máxima de rutas, comprobación del equilibrio, conteo de nodos buenos y mucho más. Pregúntese siempre: «¿qué información necesita el padre de cada hijo?». Ese es el valor de retorno. «¿Qué cálculo es local a este nodo?». Ese cálculo actualiza el resultado global. Esta descomposición es la habilidad clave para resolver problemas difíciles de árboles.
# Reusable template for post-order dual-purpose DFS:
def tree_problem(root):
result = [float('-inf')] # or 0 depending on problem
def dfs(node):
if not node:
return 0 # base return (height, count, etc.)
left_val = dfs(node.left)
right_val = dfs(node.right)
# --- Update global result using both children ---
candidate = left_val + right_val # example: diameter
result[0] = max(result[0], candidate)
# --- Return info needed by PARENT ---
return 1 + max(left_val, right_val) # example: height
dfs(root)
return result[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(tree_problem(root)) # diameter = 2Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió: cálculo de la altura mediante DFS recursivo en posorden, cálculo del diámetro en una sola pasada O(n) mediante una función auxiliar DFS de doble propósito y comprobación del equilibrio con un valor centinela de salida anticipada. A continuación, abordará los problemas de suma de rutas y del ancestro común más bajo.
Preguntas frecuentes
¿La lección «Diámetro, altura y árboles balanceados» es gratis?
Sí — el texto completo de «Diámetro, altura y árboles balanceados» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Diámetro, altura y árboles balanceados»?
Calcule el diámetro y la altura de un árbol en una sola pasada DFS mediante un helper que devuelva ambos valores y compruebe si el árbol está equilibrado por altura. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «Diámetro, altura y árboles balanceados»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Clase TreeNode y BFS por niveles
- DFS in-order, pre-order y post-order
- Diámetro, altura y árboles balanceados
- Suma de rutas y ancestro común más bajo