A parte 12 chegou a todos os nós. Esta parte é o que você calcula quando já está lá, e quase tudo se resume a uma única distinção.
Todo programa abaixo é completo, foi rodado no .NET 10, e a saída está colada da execução.
Padrão 61 — Caminhos da raiz até a folha
Colete todo caminho da raiz até uma folha, e encontre os que somam um alvo.
O caminho até aqui não pode ser devolvido para cima — é informação que vem de cima. Então ele é levado para baixo, numa lista que ganha um item na ida e perde um na volta.
// 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;
}Ele 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) depois das chamadas recursivas é o padrão inteiro. Sem isso a lista guarda todo nó já visitado e o segundo caminho sai errado. É a mesma forma de adicionar-e-desfazer sobre a qual todo o backtracking da parte 15 é construído, e vale reconhecê-la aqui primeiro, em algo pequeno.
A outra armadilha é a definição de folha. Uma folha não tem filho nenhum. Um nó com exatamente um filho não é folha — é por isso que 8 -> 4 não aparece na saída, mas 8 -> 4 -> 1 aparece. Escrever if (n.Left is null) return path.Sum(); trata um nó de um filho só como folha e produz caminhos curtos que parecem quase certos.
Custo: O(n) nós visitados; O(n·h) no total se você materializar todo caminho.
Use quando a resposta é sobre rotas completas a partir da raiz — soma de caminho, todos os caminhos, a menor string a partir de uma folha.
Padrão 62 — O que uma recursão devolve, e o que ela leva
Esta é a ideia sobre a qual o resto da parte se apoia.
Quase todo problema de árvore é um desses dois, e decidir qual decide onde a linha vai na função. Alguns precisam dos dois ao mesmo tempo — um intervalo levado para baixo, um veredito devolvido para cima.
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;
}Ele 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.Profundidade é conhecida na descida. Quando você chega num nó já sabe o quanto andou, e nenhum filho foi examinado. É um parâmetro.
Altura só é conhecida na subida. Você não sabe a altura de uma subárvore até os dois filhos responderem. É um valor de retorno.
Decidir qual das duas é a sua quantidade diz onde a linha vai na função — antes das chamadas recursivas, ou depois delas. Todo problema desta parte é uma aplicação dessa única pergunta:
| Quantidade | Direção |
|---|---|
| Profundidade, o caminho até aqui, um intervalo válido | levada para baixo, como parâmetro |
| Altura, somas de subárvores, contagens de nós | devolvida para cima, como valor |
| Diâmetro, respostas do tipo “o melhor em qualquer lugar” | devolvida para cima, e registrada fora |
Essa terceira linha é o próximo padrão.
Padrão 63 — Diâmetro, onde a resposta é um efeito colateral
O caminho mais longo entre dois nós quaisquer. O detalhe é que ele não precisa passar pela raiz — e muitas vezes não passa.
A função devolve uma altura e registra o diâmetro numa variável fora dela. A resposta é um efeito colateral, e a recursão nunca a devolve — por isso tentar transformá-la no valor de retorno é onde isto dá errado.
// 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;
}Ele 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 rootEm cada nó, o melhor caminho através dele é leftHeight + rightHeight. Então percorra a árvore calculando alturas, e em cada nó veja se o caminho que passa por ele supera o melhor visto até agora.
A função devolve uma altura. O diâmetro é registrado numa variável fora dela. São duas quantidades diferentes e a função devolve só uma delas — que é exatamente o que faz este padrão parecer estranho na primeira vez. Tentar devolver o diâmetro no lugar leva a uma confusão, porque o pai precisa da altura do filho, não do melhor caminho do filho.
Olhe o rastro. O melhor é fixado no nó 2, e a raiz reporta 4 arestas sem melhorar isso. A resposta é 6 -> 4 -> 2 -> 5 -> 7, e o nó 1 não está nela.
Custo: O(n), uma passada.
Use quando a resposta é “o melhor em qualquer lugar da árvore” e não “o melhor a partir da raiz” — soma máxima de caminho, maior caminho de valor único, maior subárvore BST. Tudo a mesma forma.
Padrão 64 — Ancestral comum mais próximo
O nó mais profundo que tem os dois alvos em algum lugar abaixo dele.
// 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;
}Ele 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) = 4Três linhas fazem tudo.
Devolva o próprio nó se ele for um dos alvos, e pare de descer. Senão pergunte aos dois filhos. Se os dois voltarem não nulos, os alvos estão em lados opostos e este nó é o ponto de encontro. Senão passe para cima o que foi encontrado.
lca(5, 4) devolver 5 não é bug. Um nó conta como ancestral de si mesmo, que é a definição usual e é por isso que a busca para assim que encontra um dos valores em vez de continuar descendo.
Numa BST nada disso é preciso. Desça comparando: se os dois alvos são menores vá para a esquerda, se os dois são maiores vá para a direita, e o primeiro nó onde eles divergem — ou que é um deles — é a resposta. Sem recursão, O(h) de tempo, O(1) de espaço.
Custo: O(n) no caso geral, O(h) numa BST.
Use quando a pergunta é sobre ancestralidade, ou a distância entre dois nós — que é depth(a) + depth(b) - 2 * depth(lca).
Padrão 65 — Validar uma BST
Aquele que quase todo mundo escreve errado na primeira vez.
Comparar um nó só com os próprios filhos aprova esta árvore: 4 < 6 é verdade, e 6 > 5 é verdade. Nada local diz ao 4 que estar na subárvore direita da raiz o obriga a passar de 5. O intervalo tem que ser levado para baixo.
// 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;
}Ele 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.A versão ingênua confere cada nó contra os filhos imediatos e aprova uma árvore que não é uma BST. Naquela árvore, 4 < 6 é verdade e 6 > 5 é verdade, então toda checagem local passa. Mas o 4 está na subárvore direita da raiz, então ele tem que passar de 5, e nada local diz isso.
A correção é informação levada para baixo, igual à profundidade. Todo nó herda um intervalo. Descer para a esquerda limita o máximo ao valor atual; descer para a direita sobe o mínimo até ele. Um nó fora do intervalo herdado falha.
Dois detalhes. Os limites são long, então um nó que guarda int.MinValue continua comparável — usar int ali faz o sentinela colidir com um valor legítimo. E as comparações são estritas, porque uma BST na definição usual não tem duplicatas.
Custo: O(n) de tempo, O(h) de espaço.
Use quando for validar qualquer propriedade estrutural que depende dos ancestrais e não do pai. “Isto é um heap válido”, “todo nó é menor que tudo acima dele” — mesma forma.
O que lembrar
-
Pergunte primeiro se a quantidade desce ou sobe. Descer significa um parâmetro, subir significa um valor de retorno. Essa única pergunta resolve a maioria dos problemas de árvore.
-
Desfaça depois das chamadas recursivas.
path.RemoveAt(path.Count - 1)não é arrumação, é o que deixa o caminho do irmão correto. -
Uma folha não tem filhos. Um nó com um filho não é folha, e tratá-lo como folha produz caminhos curtos em silêncio.
-
O diâmetro é um efeito colateral, não um valor de retorno. A função devolve a altura e registra o melhor à parte, porque o pai precisa da altura do filho.
-
O caminho mais longo muitas vezes não passa pela raiz. Se a sua solução só considera caminhos pela raiz, ela erra na maioria das árvores.
-
Um nó é ancestral de si mesmo.
lca(a, a)éa, e o retorno antecipado é o que implementa isso. -
Validar uma BST precisa de um intervalo, não de uma comparação com o pai. A checagem local aprova árvores que não são BSTs, e faz isso em silêncio.
A parte 14 deixa as árvores pelos intervalos — onde toda a dificuldade é se você ordena pelo início ou pelo fim.