Clase TreeNode y BFS por niveles
Construya árboles binarios a partir de arrays, implemente BFS con un deque para imprimir nivel por nivel y resuelva maximum-depth mediante BFS.
Clase TreeNode y BFS por niveles es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 1 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.
Fundamentos de la clase TreeNode
Un árbol binario es una estructura de datos jerárquica en la que cada nodo tiene como máximo dos hijos, llamados izquierdo y derecho. En Python, modelamos un nodo con una clase sencilla: class TreeNode: def __init__(self, val=0, left=None, right=None). Todo problema de árboles en una entrevista comienza con esta definición; la verá en el código base de prácticamente cualquier problema de árboles de LeetCode.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build a small tree manually:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)Construir árboles a partir de arreglos
En las entrevistas, a menudo se proporciona un árbol representado como un arreglo en orden por niveles, donde None indica los nodos que faltan. Dado el índice i, el hijo izquierdo se encuentra en 2i+1 y el derecho, en 2i+2. Escribir una función auxiliar que deserialice este arreglo en TreeNodes enlazados es una utilidad valiosa que ahorra tiempo durante las sesiones de práctica.
from collections import deque
def build_tree(arr):
if not arr or arr[0] is None:
return None
root = TreeNode(arr[0])
q = deque([root])
i = 1
while q and i < len(arr):
node = q.popleft()
if i < len(arr) and arr[i] is not None:
node.left = TreeNode(arr[i])
q.append(node.left)
i += 1
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
q.append(node.right)
i += 1
return root
root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)¿Qué es BFS y por qué se utiliza una cola?
La búsqueda en anchura (BFS) visita todos los nodos de profundidad d antes de visitar cualquier nodo de profundidad d+1. Este recorrido nivel por nivel es exactamente lo que proporciona una cola (FIFO): se encola la raíz, después se procesan los nodos de uno en uno y se encolan los hijos de cada nodo a medida que se avanza. collections.deque de Python proporciona appendleft y popleft en O(1), por lo que es la opción adecuada frente a una lista convencional.
from collections import deque
def bfs_print(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val, end=' ')
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root) # 1 2 3 4BFS en orden por niveles: agrupar por nivel
La variante estándar de BFS agrupa los nodos por niveles registrando el tamaño de la cola al principio de cada iteración. Procese exactamente esa cantidad de nodos, recopile sus valores y pase después al nivel siguiente. Esto produce una lista de listas, un formato de salida muy habitual en entrevistas para problemas como el recorrido de un árbol binario en orden por niveles, el recorrido en zigzag y la vista lateral derecha.
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root)) # [[1], [2, 3], [4]]Profundidad máxima mediante BFS
La profundidad máxima de un árbol binario es igual al número de niveles de su recorrido BFS. Solo tiene que contar cuántas veces completa el bucle de un nivel. Esto proporciona una solución con un tiempo de O(n) y un espacio de O(w), donde w es el ancho máximo del árbol. En un árbol equilibrado, w es O(n/2), por lo que el espacio en el peor caso es O(n).
from collections import deque
def max_depth_bfs(root):
if not root:
return 0
depth = 0
q = deque([root])
while q:
depth += 1
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return depth
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth_bfs(root)) # 3Vista lateral derecha de un árbol binario
La vista lateral derecha devuelve el último nodo visible al mirar el árbol desde la derecha, es decir, el último elemento de cada nivel en el recorrido BFS. Se trata de una aplicación directa del BFS en orden por niveles: recopile el nodo final en cada iteración de nivel. La complejidad temporal es O(n) y el espacio es O(w) para la cola.
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root)) # [1, 3, 5]Recorrido en zigzag por niveles
En el recorrido en zigzag, los niveles impares se recopilan de izquierda a derecha y los pares, de derecha a izquierda. La implementación más sencilla mantiene sin cambios la cola de BFS y simplemente invierte las listas de niveles alternos antes de añadirlas al resultado. Controle la dirección con un indicador booleano que cambie en cada nivel. Así se evita la complejidad de usar una deque de doble extremo dentro del bucle interno.
from collections import deque
def zigzag_level_order(root):
if not root:
return []
result = []
q = deque([root])
left_to_right = True
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level if left_to_right else level[::-1])
left_to_right = not left_to_right
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))Análisis de la complejidad espacial de BFS
BFS utiliza un espacio O(w), donde w es el ancho máximo del árbol. En un árbol binario perfecto con n nodos, el último nivel tiene (n+1)/2 nodos; por lo tanto, BFS puede mantener hasta n/2 nodos simultáneamente en la cola. Esto hace que BFS utilice más espacio que DFS (O(h)) en árboles equilibrados y anchos, pero menos en árboles profundos y sesgados, donde la profundidad de la pila de llamadas de DFS es igual a n.
# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)
# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)
from collections import deque
def skewed_tree(n):
root = TreeNode(1)
cur = root
for i in range(2, n+1):
cur.right = TreeNode(i)
cur = cur.right
return root
root = skewed_tree(10)
print('BFS on skewed tree is safe')Promedio de los niveles de un árbol binario
Calcular el valor promedio de cada nivel es otra aplicación directa de BFS. Sume todos los valores de un nivel, divida entre la cantidad de nodos y añada el resultado a la lista de resultados. Este problema comprueba que puede realizar operaciones aritméticas dentro del bucle de niveles. En Python 3, utilice siempre la división de tipo float (el operador /) y gestione el caso límite de un árbol vacío al principio.
from collections import deque
def average_of_levels(root):
if not root:
return []
result = []
q = deque([root])
while q:
size = len(q)
total = 0
for _ in range(size):
node = q.popleft()
total += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(total / size)
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root)) # [3.0, 14.5, 11.0]Profundidad mínima mediante BFS
La profundidad mínima es la distancia desde la raíz hasta el nodo hoja más cercano (un nodo sin hijos). BFS la encuentra de forma óptima: el primer nodo hoja encontrado durante el recorrido por niveles está necesariamente a la profundidad mínima. Devuelva la profundidad actual en cuanto encuentre una hoja. En el peor caso, la complejidad es O(n), pero en árboles equilibrados suele terminar mucho antes.
from collections import deque
def min_depth(root):
if not root:
return 0
q = deque([(root, 1)])
while q:
node, depth = q.popleft()
# A leaf has no children
if not node.left and not node.right:
return depth
if node.left:
q.append((node.left, depth + 1))
if node.right:
q.append((node.right, depth + 1))
return 0
root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5) # leaf at depth 2
print(min_depth(root)) # 2Conexión de nodos hermanos por niveles
El problema de rellenar punteros al siguiente nodo de la derecha le pide enlazar cada nodo con su vecino derecho del mismo nivel. Con BFS, esto es sencillo: dentro del bucle de cada nivel, establezca node.next = q[0] para todos los nodos excepto el último. Este es un ejemplo clásico en el que BFS hace evidente la solución, mientras que DFS requiere realizar un seguimiento cuidadoso de los punteros entre subárboles.
from collections import deque
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def connect(root):
if not root:
return root
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i < size - 1:
node.next = q[0]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return root
print('BFS connect: O(n) time, O(w) space')Comprobació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 ha aprendido: la definición de la clase TreeNode y cómo construir árboles a partir de arreglos; el BFS por niveles mediante una deque, utilizando el tamaño del nivel para agrupar los nodos; y varias aplicaciones, como la profundidad máxima, la profundidad mínima, la vista desde el lado derecho, el recorrido en zigzag y el promedio de los niveles. A continuación, exploraremos los órdenes de recorrido recursivo de DFS.
Preguntas frecuentes
¿La lección «Clase TreeNode y BFS por niveles» es gratis?
Sí — el texto completo de «Clase TreeNode y BFS por niveles» 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 «Clase TreeNode y BFS por niveles»?
Construya árboles binarios a partir de arrays, implemente BFS con un deque para imprimir nivel por nivel y resuelva maximum-depth mediante BFS. 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 1 de 4.
¿Cuánto tiempo toma la lección «Clase TreeNode y BFS por niveles»?
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