Los árboles son la otra estructura que C# no te da hecha. No existe BinaryTreeNode<T> en la BCL, así que cada programa de aquí declara uno:
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}Esta parte es solo recorrido: llegar a cada nodo, en un orden útil. La parte 13 es lo que calculas una vez que ya estás ahí.
Cada programa de abajo está completo, se ejecutó en .NET 10, y su salida está pegada de esa ejecución.
Patrón 56 — Los tres órdenes recursivos
Pre-order, in-order y post-order son la misma función tres veces. La única diferencia es en qué línea está la visita.
Las tres funciones son idénticas salvo por en qué línea está la visita. Esa única línea de diferencia es toda la distinción, y decide si un nodo se procesa antes o después de que existan las respuestas de sus hijos.
// 1
// / \
// 2 3
// / \ /
// 4 5 6
TreeNode tree = new(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5)),
new TreeNode(3, new TreeNode(6)));
// The three orders differ by ONE line: where the visit sits relative to the
// two recursive calls.
static void PreOrder(TreeNode? n, List<int> outp)
{
if (n is null) return;
outp.Add(n.Value); // visit, then children
PreOrder(n.Left, outp);
PreOrder(n.Right, outp);
}
static void InOrder(TreeNode? n, List<int> outp)
{
if (n is null) return;
InOrder(n.Left, outp);
outp.Add(n.Value); // left, visit, right
InOrder(n.Right, outp);
}
static void PostOrder(TreeNode? n, List<int> outp)
{
if (n is null) return;
PostOrder(n.Left, outp);
PostOrder(n.Right, outp);
outp.Add(n.Value); // children, then visit
}
foreach ((string name, Action<TreeNode?, List<int>> walk) in new (string, Action<TreeNode?, List<int>>)[]
{ ("pre-order ", PreOrder), ("in-order ", InOrder), ("post-order", PostOrder) })
{
List<int> got = [];
walk(tree, got);
Console.WriteLine($"{name} {string.Join(" ", got)}");
}
Console.WriteLine();
Console.WriteLine("pre-order visits a node BEFORE its subtrees -> copying a tree, serialising");
Console.WriteLine("in-order visits left, node, right -> a BST comes out sorted");
Console.WriteLine("post-order visits a node AFTER its subtrees -> freeing, or any answer that");
Console.WriteLine(" depends on both children");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}Imprime:
pre-order 1 2 4 5 3 6
in-order 4 2 5 1 6 3
post-order 4 5 2 6 3 1
pre-order visits a node BEFORE its subtrees -> copying a tree, serialising
in-order visits left, node, right -> a BST comes out sorted
post-order visits a node AFTER its subtrees -> freeing, or any answer that
depends on both childrenNombrarlos por su posición es como se enseñan normalmente, y no es lo que los hace útiles. La distinción útil es si un nodo se procesa antes o después de que existan las respuestas de sus hijos:
- Pre-order procesa un nodo sin saber nada de sus subárboles. Sirve para copiar un árbol, serializarlo, o cualquier cosa donde basten los datos del propio nodo.
- In-order sobre un árbol binario de búsqueda produce una salida ordenada. No es coincidencia: es la definición de un BST expresada como recorrido.
- Post-order procesa un nodo una vez que ambos hijos están listos. Cualquier respuesta que combine resultados de abajo es post-order, la llames así o no. Toda la parte 13 es post-order.
Costo: O(n) tiempo, O(h) espacio para la pila de llamadas, donde h es la altura.
Úsalo cuando — siempre. Este es el vocabulario en el que está escrito el resto del trabajo con árboles.
Patrón 57 — In-order sin recursión
La parte 7 dejó claro que C# termina el proceso ante un desbordamiento de pila, sin que puedas capturarlo, y que un árbol degenerado es profundo. Así que la versión iterativa importa más aquí que en otros lenguajes.
La razón por la que la gente no logra reconstruirla bajo presión es que intenta recordar el código. El código sale solo cuando nombras qué guarda la pila.
Escribir la pila a mano solo es difícil hasta que puedes nombrar qué hay en ella. Una vez que “izquierda lista, aún no visitado” es el invariante, el bucle se escribe solo — y no puede desbordarse como sí lo hace la versión recursiva en un árbol degenerado.
// 4
// / \
// 2 6
// / \ /
// 1 3 5
TreeNode tree = new(4,
new TreeNode(2, new TreeNode(1), new TreeNode(3)),
new TreeNode(6, new TreeNode(5)));
// Recursion keeps its place implicitly, on the call stack. Doing it by hand
// means the stack holds the nodes whose LEFT side is done but which have not
// themselves been visited yet.
static List<int> InOrderIterative(TreeNode? root, bool trace)
{
List<int> outp = [];
Stack<TreeNode> st = [];
TreeNode? cur = root;
while (cur is not null || st.Count > 0)
{
while (cur is not null) // go as far left as possible
{
st.Push(cur);
if (trace) Console.WriteLine($" push {cur.Value} stack=[{string.Join(",", st.Select(x => x.Value).Reverse())}]");
cur = cur.Left;
}
cur = st.Pop(); // nothing further left: visit
outp.Add(cur.Value);
if (trace) Console.WriteLine($" pop {cur.Value} visit -> [{string.Join(" ", outp)}]");
cur = cur.Right; // then handle the right subtree
}
return outp;
}
var got = InOrderIterative(tree, true);
Console.WriteLine($"\nin-order: {string.Join(" ", got)}");
Console.WriteLine($"sorted: {got.SequenceEqual(got.Order())} <- it is a BST, so in-order is sorted");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}Imprime:
push 4 stack=[4]
push 2 stack=[4,2]
push 1 stack=[4,2,1]
pop 1 visit -> [1]
pop 2 visit -> [1 2]
push 3 stack=[4,3]
pop 3 visit -> [1 2 3]
pop 4 visit -> [1 2 3 4]
push 6 stack=[6]
push 5 stack=[6,5]
pop 5 visit -> [1 2 3 4 5]
pop 6 visit -> [1 2 3 4 5 6]
in-order: 1 2 3 4 5 6
sorted: True <- it is a BST, so in-order is sortedLa pila guarda nodos cuyo subárbol izquierdo ya terminó pero que todavía no han sido visitados. Eso es exactamente lo que la pila de llamadas guardaba de forma implícita. Una vez que tienes esa frase en la cabeza, el bucle es obligado:
- Ve a la izquierda todo lo posible, apilando todo lo que encuentres.
- ¿Ya no hay nada más a la izquierda? Sácalo y visítalo: su lado izquierdo está listo por construcción.
- Luego pasa a su hijo derecho, y vuelve al paso 1.
La condición externa es cur is not null || st.Count > 0, y hacen falta las dos mitades. La pila puede estar vacía mientras todavía queda un subárbol derecho al que bajar, que es lo que pasa justo al inicio y otra vez en el nodo 4 de esa traza.
Costo: O(n) tiempo, O(h) espacio — el mismo espacio, pero en el heap, donde no puede matar el proceso.
Úsalo cuando el árbol pueda ser profundo, o cuando el problema pida pausar y reanudar el recorrido: un iterador de BST es este bucle con la parte del medio sacada.
Patrón 58 — Recorrido por niveles
Todos los patrones hasta ahora han sido en profundidad. El recorrido por niveles es en anchura, y es la misma cola de la parte 7 con un añadido.
El problema: una cola es una sola secuencia plana y no sabe nada de niveles. Los nodos del nivel 2 entran a la cola mientras el nivel 1 todavía se está vaciando, así que quedan todos mezclados.
Una cola no sabe de niveles — es una sola secuencia plana. El límite se recupera tomando una foto de cuántos nodos estaban esperando en el momento en que empezó el nivel.
// 1
// / \
// 2 3
// / \ \
// 4 5 6
// /
// 7
TreeNode tree = new(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(7))),
new TreeNode(3, null, new TreeNode(6)));
// The queue naturally mixes levels together. Capturing Count BEFORE the inner
// loop is what puts the boundaries back.
static List<List<int>> LevelOrder(TreeNode? root)
{
List<List<int>> levels = [];
if (root is null) return levels;
Queue<TreeNode> q = [];
q.Enqueue(root);
while (q.Count > 0)
{
int width = q.Count; // exactly this many nodes are on this level
List<int> level = [];
for (int i = 0; i < width; i++)
{
TreeNode n = q.Dequeue();
level.Add(n.Value);
if (n.Left is not null) q.Enqueue(n.Left);
if (n.Right is not null) q.Enqueue(n.Right);
}
levels.Add(level);
Console.WriteLine($"level {levels.Count - 1}: width was {width}, values [{string.Join(", ", level)}], queue now holds {q.Count}");
}
return levels;
}
var levels = LevelOrder(tree);
Console.WriteLine($"\nlevels: [{string.Join("], [", levels.Select(l => string.Join(", ", l)))}]");
Console.WriteLine($"depth: {levels.Count}");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}Imprime:
level 0: width was 1, values [1], queue now holds 2
level 1: width was 2, values [2, 3], queue now holds 3
level 2: width was 3, values [4, 5, 6], queue now holds 1
level 3: width was 1, values [7], queue now holds 0
levels: [1], [2, 3], [4, 5, 6], [7]
depth: 4Todo el truco es int width = q.Count; antes del bucle interno. Esa foto es cuántos nodos pertenecen a este nivel, y vaciar exactamente esa cantidad deja el límite en su sitio.
Escribe for (int i = 0; i < q.Count; i++) en su lugar y la condición se vuelve a evaluar en cada iteración contra una cola que crece a medida que se agregan hijos. El nivel nunca termina, y obtienes una sola lista plana: la traza de arriba muestra el conteo pasando de 2 a 3 a mitad de nivel, que es exactamente lo que saldría mal.
Costo: O(n) tiempo, O(w) espacio, donde w es el nivel más ancho.
Úsalo cuando el problema mencione niveles, profundidad o el más cercano. La profundidad mínima en particular debería ser BFS, no DFS: BFS puede parar en la primera hoja que encuentra, mientras que DFS tiene que explorarlo todo.
Patrón 59 — Zigzag, vistas laterales y el resto
Una vez que existe el recorrido por niveles, una cantidad sorprendente de problemas de árboles son una línea encima de él.
TreeNode tree = new(1,
new TreeNode(2, new TreeNode(4), new TreeNode(5, new TreeNode(7))),
new TreeNode(3, null, new TreeNode(6)));
static List<List<int>> Levels(TreeNode? root)
{
List<List<int>> levels = [];
if (root is null) return levels;
Queue<TreeNode> q = [];
q.Enqueue(root);
while (q.Count > 0)
{
int width = q.Count;
List<int> level = [];
for (int i = 0; i < width; i++)
{
TreeNode n = q.Dequeue();
level.Add(n.Value);
if (n.Left is not null) q.Enqueue(n.Left);
if (n.Right is not null) q.Enqueue(n.Right);
}
levels.Add(level);
}
return levels;
}
var levels = Levels(tree);
// Zigzag: do NOT alternate the traversal. Reverse alternate rows afterwards.
var zigzag = levels.Select((l, i) => i % 2 == 1 ? Enumerable.Reverse(l).ToList() : l).ToList();
// Right side view: the last value of each level.
var rightView = levels.Select(l => l[^1]).ToList();
// Left side view is the first of each level, for free.
var leftView = levels.Select(l => l[0]).ToList();
Console.WriteLine($"levels : [{string.Join("], [", levels.Select(l => string.Join(", ", l)))}]");
Console.WriteLine($"zigzag : [{string.Join("], [", zigzag.Select(l => string.Join(", ", l)))}]");
Console.WriteLine($"right view : {string.Join(", ", rightView)}");
Console.WriteLine($"left view : {string.Join(", ", leftView)}");
Console.WriteLine($"max depth : {levels.Count}");
Console.WriteLine($"widest : {levels.Max(l => l.Count)} nodes, at level {levels.FindIndex(l => l.Count == levels.Max(x => x.Count))}");
Console.WriteLine();
Console.WriteLine("Every one of these is the level list plus one line. Trying to build");
Console.WriteLine("zigzag by alternating the traversal itself is where people tie themselves");
Console.WriteLine("in knots — the queue order stays the same, only the output is reversed.");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}Imprime:
levels : [1], [2, 3], [4, 5, 6], [7]
zigzag : [1], [3, 2], [4, 5, 6], [7]
right view : 1, 3, 6, 7
left view : 1, 2, 4, 7
max depth : 4
widest : 3 nodes, at level 2
Every one of these is the level list plus one line. Trying to build
zigzag by alternating the traversal itself is where people tie themselves
in knots — the queue order stays the same, only the output is reversed.El zigzag es donde la gente se enreda, porque el instinto es alternar el recorrido: encolar la derecha antes que la izquierda en los niveles impares, o cambiar la cola por una pila. Eso funciona, es engorroso y es fácil equivocarse.
El orden de la cola no necesita cambiar. Construye los niveles normalmente, y después invierte las filas alternas. Misma respuesta, una línea, nada que depurar.
Las vistas laterales son el último y el primer elemento de cada nivel. La profundidad máxima es el conteo. El nivel más ancho es un Max. Ninguna de estas necesita su propio algoritmo.
Úsalo cuando cualquier pregunta esté planteada por nivel. Construye los niveles, y después responde la pregunta sobre la lista.
Patrón 60 — Reconstruir un árbol a partir de dos recorridos
Dados el pre-order y el in-order, reconstruye el árbol.
Un solo recorrido nunca alcanza: muchos árboles distintos comparten un mismo pre-order. Dos, con el in-order entre ellos, lo fijan exactamente.
Encuentra la posición de la raíz en el arreglo in-order con un diccionario, no con un barrido. Un barrido hace que cada nivel sea O(n) y toda la reconstrucción O(n²) en un árbol degenerado — que es exactamente la entrada que va a usar un test.
int[] preorder = [1, 2, 4, 5, 3, 6];
int[] inorder = [4, 2, 5, 1, 6, 3];
// pre-order gives you the ROOT first. in-order tells you how much of the rest
// belongs on each side of it. A dictionary makes "where is the root in inorder"
// O(1) instead of a scan, which is the difference between O(n) and O(n^2).
Dictionary<int, int> where = inorder.Select((v, i) => (v, i)).ToDictionary(t => t.v, t => t.i);
int cursor = 0;
TreeNode? Build(int lo, int hi, int depth)
{
if (lo > hi) return null;
int value = preorder[cursor++];
int mid = where[value];
Console.WriteLine($"{new string(' ', depth * 2)}root {value}: inorder[{lo}..{hi}], splits at {mid} " +
$"-> left [{lo}..{mid - 1}], right [{mid + 1}..{hi}]");
var node = new TreeNode(value);
node.Left = Build(lo, mid - 1, depth + 1); // must come first: it consumes
node.Right = Build(mid + 1, hi, depth + 1); // the pre-order cursor in order
return node;
}
TreeNode? root = Build(0, inorder.Length - 1, 0);
static void Pre(TreeNode? n, List<int> o) { if (n is null) return; o.Add(n.Value); Pre(n.Left, o); Pre(n.Right, o); }
static void In(TreeNode? n, List<int> o) { if (n is null) return; In(n.Left, o); o.Add(n.Value); In(n.Right, o); }
List<int> p = [], i = [];
Pre(root, p); In(root, i);
Console.WriteLine($"\nrebuilt pre-order: {string.Join(" ", p)} matches: {p.SequenceEqual(preorder)}");
Console.WriteLine($"rebuilt in-order : {string.Join(" ", i)} matches: {i.SequenceEqual(inorder)}");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}Imprime:
root 1: inorder[0..5], splits at 3 -> left [0..2], right [4..5]
root 2: inorder[0..2], splits at 1 -> left [0..0], right [2..2]
root 4: inorder[0..0], splits at 0 -> left [0..-1], right [1..0]
root 5: inorder[2..2], splits at 2 -> left [2..1], right [3..2]
root 3: inorder[4..5], splits at 5 -> left [4..4], right [6..5]
root 6: inorder[4..4], splits at 4 -> left [4..3], right [5..4]
rebuilt pre-order: 1 2 4 5 3 6 matches: True
rebuilt in-order : 4 2 5 1 6 3 matches: TrueDos cosas lo sostienen.
El primer valor no consumido del pre-order siempre es la siguiente raíz. Un único cursor compartido lo avanza, y por eso Build(left) debe llamarse antes que Build(right): el subárbol izquierdo consume primero su parte del pre-order. Intercambia esas dos líneas y el árbol sale reflejado, sin ningún error.
El in-order dice dónde partir. Todo lo que está a la izquierda de la posición de la raíz pertenece al subárbol izquierdo, y todo lo que está a la derecha, al derecho. El diccionario where hace esa búsqueda O(1); barrer el arreglo in-order en su lugar hace que toda la reconstrucción sea O(n²) en un árbol degenerado, que es precisamente la entrada que va a elegir un caso de prueba.
Fíjate en que el caso base lo > hi maneja los rangos vacíos de la traza: [0..-1] y [2..1] son la forma en que un hijo ausente se anuncia.
Post-order más in-order funciona igual, consumiendo el post-order hacia atrás y construyendo la derecha antes que la izquierda. Pre-order más post-order no determina un árbol de forma única.
Costo: O(n) tiempo y espacio.
Úsalo cuando te entreguen dos recorridos, o cuando serialices y deserialices un árbol.
Qué recordar
-
Los tres órdenes se diferencian por una línea. Lo que importa es si un nodo se procesa antes o después de que existan las respuestas de sus hijos.
-
In-order sobre un BST sale ordenado. Esa es la definición, recorrida.
-
La pila iterativa guarda “izquierda lista, aún no visitado”. Nombra el invariante y el código sale solo; memorizar el código no sobrevive a la presión.
-
Guarda
q.Counten una variable local antes de vaciar un nivel. Volver a leerlo en la condición del bucle significa que el nivel nunca termina. -
No alternes el recorrido para el zigzag. Construye los niveles e invierte las filas alternas.
-
Construye el subárbol izquierdo antes que el derecho. Comparten un solo cursor del pre-order, y el orden de esas dos llamadas es toda la diferencia entre un árbol y su reflejo.
-
Indexa el arreglo in-order con un diccionario. Barrer convierte O(n) en O(n²) justo en la entrada que va a elegir un test.
La parte 13 es lo que haces una vez que puedes llegar a cada nodo: sumas de caminos, diámetro, ancestros, y la distinción entre lo que una recursión devuelve y lo que lleva hacia abajo.