Suma de rutas y ancestro común más bajo
Resuelva root-to-leaf path sum, all-paths-sum y lowest-common-ancestor para un árbol binario general mediante descenso recursivo.
Suma de rutas y ancestro común más bajo es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 4 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 DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Suma de rutas de la raíz a una hoja
El problema de la suma de rutas pregunta si alguna ruta de la raíz a una hoja tiene una suma igual a un objetivo. Pase el objetivo restante durante la recursión, restando el valor de cada nodo. En una hoja, compruebe si el valor restante es igual al valor de la hoja. Esto evita mantener una lista de rutas explícita y es eficiente en cuanto al espacio y clara. Caso extremo: un árbol vacío no tiene rutas, por lo que debe devolver False inmediatamente.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def has_path_sum(root, target):
if not root:
return False
if not root.left and not root.right: # leaf
return root.val == target
remain = target - root.val
return (has_path_sum(root.left, remain) or
has_path_sum(root.right, remain))
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->2Todas las rutas de la raíz a una hoja
Para enumerar todas las rutas, mantenga una lista de la ruta acumulada. En cada llamada recursiva, añada el valor del nodo actual, recurra en los hijos y luego haga pop al regresar (retroceso). En una hoja, registre una instantánea (list(path)) de la ruta actual. Este patrón —elegir, recurrir y deshacer la elección— es la base del retroceso en árboles.
def all_path_sums(root, target):
results = []
def dfs(node, path, remaining):
if not node:
return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
results.append(list(path)) # snapshot
else:
dfs(node.left, path, remaining - node.val)
dfs(node.right, path, remaining - node.val)
path.pop() # backtrack
dfs(root, [], target)
return results
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(5)
print(all_path_sums(root, 22)) # [[5,4,11,2]]Suma de rutas III: cualquier ruta, cualquier nodo
Path Sum III (LeetCode #437) cuenta las rutas cuya suma es igual a un objetivo, donde la ruta puede comenzar y terminar en cualquier lugar (no solo de la raíz a una hoja). La fuerza bruta tiene una complejidad O(n²): ejecute un DFS desde cada nodo. El enfoque óptimo O(n) utiliza un mapa hash de sumas prefijas: realice un seguimiento de la suma acumulada y cuente cuántas veces apareció antes current_sum - target, siguiendo el enfoque de suma de subarreglos.
def path_sum_iii(root, target):
prefix_counts = {0: 1}
def dfs(node, running_sum):
if not node:
return 0
running_sum += node.val
count = prefix_counts.get(running_sum - target, 0)
prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
count += dfs(node.left, running_sum)
count += dfs(node.right, running_sum)
prefix_counts[running_sum] -= 1 # backtrack
return count
return dfs(root, 0)
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(-3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.right = TreeNode(11)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(-2)
root.left.right.right = TreeNode(1)
print(path_sum_iii(root, 8)) # 3¿Qué es el ancestro común más bajo?
El ancestro común más bajo (LCA) de dos nodos p y q en un árbol binario es el nodo más profundo que tiene a p y q como descendientes (un nodo puede ser descendiente de sí mismo). LCA aparece en problemas como «distancia entre dos nodos», «ruta entre dos nodos» y consultas de rangos en BST. Comprender LCA es fundamental para resolver problemas intermedios de árboles.
# 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
# LCA(5, 1) = 3 (root)
# LCA(5, 4) = 5 (p itself is ancestor of q)
# LCA(6, 4) = 5
# LCA(7, 4) = 2
# Key insight: the LCA is the node where p and q
# first 'split' into different subtrees.
print('LCA: deepest node that is ancestor of both p and q')Algoritmo recursivo para LCA
La elegante solución recursiva para LCA devuelve el primer nodo que es p o q, o que tiene ambos en sus subárboles. Si el nodo actual es p o q, devuélvalo. De lo contrario, recurra a la izquierda y a la derecha. Si ambos lados devuelven un valor distinto de null, el nodo actual es el LCA. Si solo un lado devuelve un valor distinto de null, propague ese resultado hacia arriba. Esto tiene una complejidad temporal O(n) y espacial O(h).
def lowest_common_ancestor(root, p, q):
# Base case: empty or found one of the targets
if not root or root == p or root == q:
return root
# Search both subtrees
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
# If both sides found something, this node is the LCA
if left and right:
return root
# Otherwise, return whichever side found something
return left if left else right
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
p, q = root.left, root.right # 5 and 1
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 3LCA cuando un nodo puede ser su propio ancestro
Un caso extremo importante: si p es ancestro de q (o viceversa), el LCA es p mismo. El algoritmo recursivo lo gestiona automáticamente: cuando llega a p, devuelve p inmediatamente sin explorar los subárboles de p. El padre verá que un lado ha devuelto p y el otro ha devuelto null, por lo que propagará p hacia arriba como el LCA. Verifique siempre este caso en sus pruebas al programar LCA.
# Test case: p is ancestor of q
# Tree: 3 -> left=5 -> left=6
# LCA(5, 6) should be 5
root = TreeNode(3)
root.left = TreeNode(5)
root.left.left = TreeNode(6)
p = root.left # node 5
q = root.left.left # node 6
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 5 (p itself is the LCA)LCA con punteros al padre
Si cada nodo tiene un puntero al padre, LCA se reduce al problema de la «intersección de dos listas enlazadas». Reúna los ancestros de p en un conjunto y luego recorra hacia arriba desde q hasta encontrar un nodo que pertenezca a ese conjunto. Este enfoque, con una complejidad temporal O(h) y espacial O(h), es común en entrevistas de diseño de sistemas en las que controla la estructura de los nodos y puede almacenar referencias al padre.
class NodeWithParent:
def __init__(self, val, parent=None):
self.val = val
self.parent = parent
self.left = None
self.right = None
def lca_with_parent(p, q):
ancestors = set()
# Collect all ancestors of p
node = p
while node:
ancestors.add(node)
node = node.parent
# Walk up from q until we hit a known ancestor
node = q
while node:
if node in ancestors:
return node
node = node.parent
return None
print('With parent pointers: O(h) time and space')LCA en un árbol binario de búsqueda
En un BST, LCA es más sencillo porque la propiedad de orden indica en qué subárbol se encuentra cada nodo. Si p y q son menores que el nodo actual, el LCA está en el subárbol izquierdo. Si ambos son mayores, está en el subárbol derecho. De lo contrario, el nodo actual los separa, por lo que es el LCA. Esto reduce el problema a O(log n) en BST equilibrados.
def lca_bst(root, p, q):
if not root:
return None
if p.val < root.val and q.val < root.val:
return lca_bst(root.left, p, q) # both in left
if p.val > root.val and q.val > root.val:
return lca_bst(root.right, p, q) # both in right
return root # split point = LCA
# Iterative BST LCA (no recursion overhead):
def lca_bst_iter(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
return None
print('BST LCA: O(log n) for balanced trees')Distancia entre dos nodos
La distancia entre dos nodos en un árbol equivale al número de aristas de la ruta que los conecta. Se calcula directamente a partir del LCA: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Primero encuentre el LCA y luego cuente la profundidad de cada nodo. Con una función auxiliar adecuada, esto tiene una complejidad temporal O(n) y espacial O(h).
def find_depth(root, target, depth=0):
if not root:
return -1
if root == target:
return depth
left = find_depth(root.left, target, depth + 1)
if left != -1:
return left
return find_depth(root.right, target, depth + 1)
def node_distance(root, p, q):
lca = lowest_common_ancestor(root, p, q)
# depth from LCA to p and q
dp = find_depth(lca, p)
dq = find_depth(lca, q)
return dp + dq
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(node_distance(root, root.left.left, root.left.right)) # 2Ruta de suma máxima de la raíz a una hoja
La ruta de suma máxima de la raíz a una hoja realiza un seguimiento de la suma acumulada desde la raíz hasta el nodo actual. En las hojas, compárela con un máximo global. Este es un DFS en preorden en el que la suma de la ruta actual se pasa como parámetro. A diferencia de la suma máxima de rutas genérica, esta versión está limitada a rutas de la raíz a una hoja, por lo que es más sencilla: no es necesario considerar rutas arbitrarias entre nodos.
def max_root_to_leaf_sum(root):
if not root:
return float('-inf')
best = [float('-inf')]
def dfs(node, running):
running += node.val
if not node.left and not node.right: # leaf
best[0] = max(best[0], running)
return
if node.left:
dfs(node.left, running)
if node.right:
dfs(node.right, running)
dfs(root, 0)
return best[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(max_root_to_leaf_sum(root)) # 1+2+5 = 8Suma de números de la raíz a una hoja
Sum root-to-leaf numbers (LeetCode #129) trata cada ruta de la raíz a una hoja como un número decimal (por ejemplo, la ruta 1→2→3 representa el número 123) y solicita su suma. Construya el número pasando current_number * 10 + node.val durante la recursión. En cada hoja, añada el número completo al total. Este es un ejemplo claro de DFS en preorden que pasa el estado acumulado hacia abajo.
def sum_numbers(root):
def dfs(node, num):
if not node:
return 0
num = num * 10 + node.val
if not node.left and not node.right: # leaf
return num
return dfs(node.left, num) + dfs(node.right, num)
return dfs(root, 0)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(sum_numbers(root)) # 12 + 13 = 25
root2 = TreeNode(4)
root2.left = TreeNode(9)
root2.right = TreeNode(0)
root2.left.left = TreeNode(5)
root2.left.right = TreeNode(1)
print(sum_numbers(root2)) # 495 + 491 + 40 = 1026Comprobació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ó: variantes de la suma de rutas (de la raíz a una hoja, todas las rutas y Path Sum III con sumas prefijas), ancestro común más bajo mediante una elegante división recursiva y LCA en BST en O(log n) usando la propiedad de orden. A continuación, comenzará con los árboles binarios de búsqueda mediante operaciones de inserción y búsqueda.
Preguntas frecuentes
¿La lección «Suma de rutas y ancestro común más bajo» es gratis?
Sí — el texto completo de «Suma de rutas y ancestro común más bajo» 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 DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Suma de rutas y ancestro común más bajo»?
Resuelva root-to-leaf path sum, all-paths-sum y lowest-common-ancestor para un árbol binario general mediante descenso recursivo. Practicas DSA 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 DSA Interview Prep?
No se requiere experiencia previa. DSA 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 4 de 4.
¿Cuánto tiempo toma la lección «Suma de rutas y ancestro común más bajo»?
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 DSA Interview Prep?
Sí. Cada lección de DSA 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