La parte 12 llegó a cada nodo. Esta parte es lo que calculas una vez que estás ahí, y casi todo se reduce a una sola distinción.
Cada programa de abajo está completo, se ejecutó en .NET 10, y su salida está pegada de la corrida.
Patrón 61 — Caminos de la raíz a la hoja
Reúne todos los caminos de la raíz a una hoja, y encuentra los que suman un objetivo.
El camino recorrido no se puede retornar hacia arriba: es información que viene de arriba. Así que se lleva hacia abajo, en una lista a la que le agregas al entrar y le quitas al salir.
// 5
// / \
// 4 8
// / / \
// 11 13 4
// / \ \
// 7 2 1
TreeNode tree = new(5,
new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))),
new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))));
// The path so far is CARRIED DOWN in a list that is mutated and then undone.
// That undo is the same move backtracking is built on — see part 15.
static void Paths(TreeNode? n, List<int> path, List<string> found, int target)
{
if (n is null) return;
path.Add(n.Value);
bool isLeaf = n.Left is null && n.Right is null;
if (isLeaf)
{
int sum = path.Sum();
string mark = sum == target ? " <- sums to " + target : "";
found.Add($"{string.Join(" -> ", path),-22} = {sum,3}{mark}");
}
else
{
Paths(n.Left, path, found, target);
Paths(n.Right, path, found, target);
}
path.RemoveAt(path.Count - 1); // undo, so a sibling starts clean
}
List<string> found = [];
Paths(tree, [], found, 22);
foreach (string s in found) Console.WriteLine(s);
Console.WriteLine();
Console.WriteLine("A leaf is a node with NO children. A node with one child is not a leaf,");
Console.WriteLine("which is why 8 -> 4 -> 1 is a path and 8 -> 4 is not.");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}Imprime:
5 -> 4 -> 11 -> 7 = 27
5 -> 4 -> 11 -> 2 = 22 <- sums to 22
5 -> 8 -> 13 = 26
5 -> 8 -> 4 -> 1 = 18
A leaf is a node with NO children. A node with one child is not a leaf,
which is why 8 -> 4 -> 1 is a path and 8 -> 4 is not.path.RemoveAt(path.Count - 1) después de las llamadas recursivas es todo el patrón. Sin eso, la lista se queda con cada nodo que alguna vez visitaste y el segundo camino sale mal. Es la misma forma de agregar-y-deshacer sobre la que está construido todo el backtracking de la parte 15, y vale la pena reconocerla aquí primero, en algo pequeño.
La otra trampa es la definición de hoja. Una hoja no tiene hijos en absoluto. Un nodo con exactamente un hijo no es una hoja: por eso 8 -> 4 no aparece en la salida pero 8 -> 4 -> 1 sí. Escribir if (n.Left is null) return path.Sum(); trata un nodo con un solo hijo como hoja y produce caminos cortos que se ven casi correctos.
Costo: O(n) nodos visitados; O(n·h) en total si materializas cada camino.
Úsalo cuando la respuesta es sobre rutas completas desde la raíz: suma de camino, todos los caminos, la cadena más pequeña desde una hoja.
Patrón 62 — Lo que retorna una recursión, y lo que lleva
Esta es la idea sobre la que descansa el resto de la parte.
Casi todo problema de árboles es uno de estos dos, y decidir cuál es decide dónde va la línea en la función. Algunos necesitan los dos a la vez — un rango llevado hacia abajo, un veredicto retornado hacia arriba.
TreeNode tree = new(5,
new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2))),
new TreeNode(8, new TreeNode(13), new TreeNode(4, null, new TreeNode(1))));
// CARRIED DOWN: the parameter. Information flowing from the root towards leaves.
static void CarryDown(TreeNode? n, int depth, List<string> log)
{
if (n is null) return;
log.Add($" node {n.Value,2} is at depth {depth}");
CarryDown(n.Left, depth + 1, log);
CarryDown(n.Right, depth + 1, log);
}
// RETURNED UP: the return value. Information flowing from leaves to the root.
static int ReturnUp(TreeNode? n)
{
if (n is null) return 0;
int left = ReturnUp(n.Left);
int right = ReturnUp(n.Right);
return 1 + Math.Max(left, right); // needs BOTH children's answers first
}
List<string> log = [];
CarryDown(tree, 0, log);
Console.WriteLine("carried down (a parameter) — depth of each node:");
foreach (string s in log) Console.WriteLine(s);
Console.WriteLine($"\nreturned up (a return value) — height of the tree: {ReturnUp(tree)}");
Console.WriteLine();
Console.WriteLine("Depth is known on the way DOWN, before any child is examined.");
Console.WriteLine("Height is only known on the way UP, after both children have answered.");
Console.WriteLine("Deciding which one a quantity is tells you where the line goes.");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}Imprime:
carried down (a parameter) — depth of each node:
node 5 is at depth 0
node 4 is at depth 1
node 11 is at depth 2
node 7 is at depth 3
node 2 is at depth 3
node 8 is at depth 1
node 13 is at depth 2
node 4 is at depth 2
node 1 is at depth 3
returned up (a return value) — height of the tree: 4
Depth is known on the way DOWN, before any child is examined.
Height is only known on the way UP, after both children have answered.
Deciding which one a quantity is tells you where the line goes.La profundidad se sabe en el camino hacia abajo. Cuando llegas a un nodo ya sabes qué tan lejos has llegado, y ningún hijo ha sido examinado. Es un parámetro.
La altura solo se sabe en el camino hacia arriba. No puedes decir qué tan alto es un subárbol hasta que ambos hijos hayan reportado. Es un valor de retorno.
Decidir cuál de las dos es tu cantidad te dice dónde va la línea en la función: antes de las llamadas recursivas, o después de ellas. Cada problema de esta parte es una aplicación de esa única pregunta:
| Cantidad | Dirección |
|---|---|
| Profundidad, el camino recorrido, un rango válido | llevada hacia abajo, como parámetro |
| Altura, sumas de subárboles, conteos de nodos | retornada hacia arriba, como valor |
| Diámetro, respuestas del tipo “el mejor en cualquier parte” | retornada hacia arriba, y registrada afuera |
Esa tercera fila es el siguiente patrón.
Patrón 63 — Diámetro, donde la respuesta es un efecto secundario
El camino más largo entre dos nodos cualesquiera. El detalle es que no tiene que pasar por la raíz, y muy seguido no lo hace.
La función retorna una altura y registra el diámetro en una variable fuera de ella. La respuesta es un efecto secundario, y la recursión nunca la retorna — por eso intentar convertirla en el valor de retorno es donde esto se tuerce.
// 1
// / \
// 2 3
// / \
// 4 5
// / \
// 6 7
TreeNode tree = new(1,
new TreeNode(2, new TreeNode(4, new TreeNode(6)), new TreeNode(5, null, new TreeNode(7))),
new TreeNode(3));
// The longest path in a tree need not pass through the root. At every node the
// best path THROUGH it is left height + right height. The answer is the largest
// of those — which is a SIDE EFFECT of a function that returns something else.
int best = 0;
int Height(TreeNode? n, int depth)
{
if (n is null) return 0;
int left = Height(n.Left, depth + 1);
int right = Height(n.Right, depth + 1);
int through = left + right; // edges, counting through this node
if (through > best)
{
best = through;
Console.WriteLine($"{new string(' ', depth * 2)}node {n.Value}: left={left} right={right} -> path of {through} edges through it (new best)");
}
else
{
Console.WriteLine($"{new string(' ', depth * 2)}node {n.Value}: left={left} right={right} -> {through} edges, best stays {best}");
}
return 1 + Math.Max(left, right); // the RETURN value is the height
}
Height(tree, 0);
Console.WriteLine($"\ndiameter: {best} edges");
Console.WriteLine("the path is 6 -> 4 -> 2 -> 5 -> 7, which never touches the root");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}Imprime:
node 6: left=0 right=0 -> 0 edges, best stays 0
node 4: left=1 right=0 -> path of 1 edges through it (new best)
node 7: left=0 right=0 -> 0 edges, best stays 1
node 5: left=0 right=1 -> 1 edges, best stays 1
node 2: left=2 right=2 -> path of 4 edges through it (new best)
node 3: left=0 right=0 -> 0 edges, best stays 4
node 1: left=3 right=1 -> 4 edges, best stays 4
diameter: 4 edges
the path is 6 -> 4 -> 2 -> 5 -> 7, which never touches the rootEn cada nodo, el mejor camino a través de ese nodo es leftHeight + rightHeight. Así que recorre el árbol calculando alturas, y en cada nodo revisa si el camino a través de él supera al mejor visto hasta ahora.
La función retorna una altura. El diámetro se registra en una variable fuera de ella. Son dos cantidades distintas y la función solo retorna una de ellas, que es justo lo que hace que este patrón se sienta raro la primera vez. Intentar retornar el diámetro en su lugar termina en un enredo, porque un padre necesita la altura de su hijo, no el mejor camino de su hijo.
Mira la traza. El mejor se fija en el nodo 2, y la raíz reporta 4 aristas sin mejorarlo. La respuesta es 6 -> 4 -> 2 -> 5 -> 7, y el nodo 1 no está en ella.
Costo: O(n), una sola pasada.
Úsalo cuando la respuesta es “el mejor en cualquier parte del árbol” en vez de “el mejor desde la raíz”: suma máxima de camino, camino univalor más largo, mayor subárbol BST. Todos tienen la misma forma.
Patrón 64 — Ancestro común más bajo
El nodo más profundo que tiene ambos objetivos en algún lugar debajo de él.
// 3
// / \
// 5 1
// / \ / \
// 6 2 0 8
// / \
// 7 4
TreeNode tree = new(3,
new TreeNode(5, new TreeNode(6), new TreeNode(2, new TreeNode(7), new TreeNode(4))),
new TreeNode(1, new TreeNode(0), new TreeNode(8)));
// Return the node itself if found, otherwise whatever the children found.
// A node that hears back from BOTH sides is the meeting point.
static TreeNode? Lca(TreeNode? n, int a, int b)
{
if (n is null) return null;
if (n.Value == a || n.Value == b) return n; // found one; stop descending
TreeNode? left = Lca(n.Left, a, b);
TreeNode? right = Lca(n.Right, a, b);
if (left is not null && right is not null) return n; // one on each side
return left ?? right; // pass the survivor up
}
foreach ((int a, int b) in new[] { (5, 1), (5, 4), (7, 4), (6, 8), (5, 5) })
Console.WriteLine($"lca({a}, {b}) = {Lca(tree, a, b)!.Value}");
Console.WriteLine();
Console.WriteLine("lca(5, 4) is 5: a node is allowed to be its own ancestor, which is why");
Console.WriteLine("the search stops the moment it finds either value rather than going deeper.");
Console.WriteLine();
// In a BST you do not need any of that — the values tell you which way to go.
static TreeNode? LcaBst(TreeNode? n, int a, int b)
{
while (n is not null)
{
if (a < n.Value && b < n.Value) n = n.Left;
else if (a > n.Value && b > n.Value) n = n.Right;
else return n; // they diverge here, or one IS here
}
return null;
}
TreeNode bst = new(6,
new TreeNode(2, new TreeNode(0), new TreeNode(4, new TreeNode(3), new TreeNode(5))),
new TreeNode(8, new TreeNode(7), new TreeNode(9)));
Console.WriteLine("in a BST, no recursion is needed at all:");
foreach ((int a, int b) in new[] { (2, 8), (2, 4), (3, 5) })
Console.WriteLine($" lca({a}, {b}) = {LcaBst(bst, a, b)!.Value}");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}Imprime:
lca(5, 1) = 3
lca(5, 4) = 5
lca(7, 4) = 2
lca(6, 8) = 3
lca(5, 5) = 5
lca(5, 4) is 5: a node is allowed to be its own ancestor, which is why
the search stops the moment it finds either value rather than going deeper.
in a BST, no recursion is needed at all:
lca(2, 8) = 6
lca(2, 4) = 2
lca(3, 5) = 4Tres líneas hacen todo.
Retorna el nodo mismo si es uno de los objetivos, y deja de descender. Si no, pregúntales a los dos hijos. Si ambos regresan algo no nulo, los objetivos están en lados opuestos y este nodo es el punto de encuentro. Si no, pasa hacia arriba el que sí se encontró.
Que lca(5, 4) retorne 5 no es un error. Un nodo cuenta como su propio ancestro, que es la definición habitual, y es por eso que la búsqueda se detiene apenas encuentra cualquiera de los dos valores en vez de seguir bajando.
En un BST nada de esto hace falta. Baja comparando: si ambos objetivos son menores ve a la izquierda, si ambos son mayores ve a la derecha, y el primer nodo donde divergen —o que es uno de ellos— es la respuesta. Sin recursión, O(h) de tiempo, O(1) de espacio.
Costo: O(n) en general, O(h) en un BST.
Úsalo cuando la pregunta es sobre ancestros, o sobre la distancia entre dos nodos, que es depth(a) + depth(b) - 2 * depth(lca).
Patrón 65 — Validar un BST
El que casi todos escriben mal la primera vez.
Comparar un nodo solo con sus propios hijos aprueba este árbol: 4 < 6 es cierto, y 6 > 5 es cierto. Nada local le dice nunca a 4 que estar en el subárbol derecho de la raíz lo obliga a superar a 5. El rango tiene que llevarse hacia abajo.
// 5 5 is the root, and 4 sits in its RIGHT subtree.
// / \ Every parent-child pair is individually fine.
// 1 6 The tree is still not a BST.
// / \
// 4 7
TreeNode broken = new(5,
new TreeNode(1),
new TreeNode(6, new TreeNode(4), new TreeNode(7)));
TreeNode fine = new(5,
new TreeNode(3, new TreeNode(1), new TreeNode(4)),
new TreeNode(8, new TreeNode(6), new TreeNode(9)));
// WRONG: only compares a node with its immediate children.
static bool NaiveCheck(TreeNode? n)
{
if (n is null) return true;
if (n.Left is not null && n.Left.Value >= n.Value) return false;
if (n.Right is not null && n.Right.Value <= n.Value) return false;
return NaiveCheck(n.Left) && NaiveCheck(n.Right);
}
// RIGHT: every node inherits a range from its ancestors, and must fall inside it.
static bool Check(TreeNode? n, long low, long high)
{
if (n is null) return true;
if (n.Value <= low || n.Value >= high) return false;
return Check(n.Left, low, n.Value) && Check(n.Right, n.Value, high);
}
foreach ((string name, TreeNode t) in new[] { ("broken", broken), ("fine ", fine) })
Console.WriteLine($"{name} naive says {NaiveCheck(t),-5} bounds say {Check(t, long.MinValue, long.MaxValue)}");
Console.WriteLine();
Console.WriteLine("The naive check passes the broken tree because 4 < 6 and 6 > 5 are both");
Console.WriteLine("true locally. Nothing ever told 4 that it had to be greater than 5.");
Console.WriteLine();
Console.WriteLine("Bounds narrow on the way down: going left caps the maximum at the node's");
Console.WriteLine("value, going right raises the minimum to it. That is carried-down");
Console.WriteLine("information, exactly like depth.");
Console.WriteLine();
Console.WriteLine("long is used for the bounds so a node holding int.MinValue still works.");
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}Imprime:
broken naive says True bounds say False
fine naive says True bounds say True
The naive check passes the broken tree because 4 < 6 and 6 > 5 are both
true locally. Nothing ever told 4 that it had to be greater than 5.
Bounds narrow on the way down: going left caps the maximum at the node's
value, going right raises the minimum to it. That is carried-down
information, exactly like depth.
long is used for the bounds so a node holding int.MinValue still works.La versión ingenua revisa cada nodo contra sus hijos inmediatos y aprueba un árbol que no es un BST. En ese árbol, 4 < 6 es cierto y 6 > 5 es cierto, así que cada revisión local pasa. Pero 4 está en el subárbol derecho de la raíz, o sea que debe superar a 5, y nada local lo dice nunca.
La solución es información llevada hacia abajo, igual que la profundidad. Cada nodo hereda un rango. Bajar a la izquierda limita el máximo al valor actual; bajar a la derecha sube el mínimo hasta él. Un nodo fuera del rango que heredó falla.
Dos detalles. Los límites son long, así que un nodo que guarda int.MinValue sigue siendo comparable: usar int ahí hace que el centinela choque con un valor legítimo. Y las comparaciones son estrictas, porque un BST, tal como se define normalmente, no tiene duplicados.
Costo: O(n) de tiempo, O(h) de espacio.
Úsalo cuando valides cualquier propiedad estructural que dependa de los ancestros y no de los padres. “¿Es este un heap válido?”, “¿es cada nodo menor que todo lo que está arriba de él?”: la misma forma.
Qué recordar
-
Pregunta primero si la cantidad viaja hacia abajo o hacia arriba. Hacia abajo significa un parámetro, hacia arriba significa un valor de retorno. Esa sola pregunta resuelve la mayoría de los problemas de árboles.
-
Deshaz después de las llamadas recursivas.
path.RemoveAt(path.Count - 1)no es ordenar la casa, es lo que hace que el camino de un hermano salga correcto. -
Una hoja no tiene hijos. Un nodo con un hijo no lo es, y tratarlo como si lo fuera produce caminos cortos en silencio.
-
El diámetro es un efecto secundario, no un valor de retorno. La función retorna la altura y registra el mejor por separado, porque un padre necesita la altura del hijo.
-
El camino más largo muchas veces no pasa por la raíz. Si tu solución solo considera caminos a través de la raíz, está mal en la mayoría de los árboles.
-
Un nodo es su propio ancestro.
lca(a, a)esa, y el retorno temprano es lo que implementa eso. -
Validar un BST necesita un rango, no una comparación con el padre. La revisión local aprueba árboles que no son BST, y lo hace calladamente.
La parte 14 deja los árboles por los intervalos, donde toda la dificultad está en si ordenas por el inicio o por el final.