Árvores são a outra estrutura que o C# não te entrega pronta. Não existe BinaryTreeNode<T> na BCL, então todo programa aqui declara um:
class TreeNode(int value, TreeNode? left = null, TreeNode? right = null)
{
public int Value = value;
public TreeNode? Left = left, Right = right;
}Esta parte é só percurso — chegar a todo nó, numa ordem útil. A parte 13 é o que você calcula depois de chegar lá.
Todo programa abaixo é completo, foi rodado no .NET 10, e a saída está colada da execução.
Padrão 56 — As três ordens recursivas
Pré-ordem, em ordem e pós-ordem são a mesma função três vezes. A única diferença é em que linha a visita fica.
As três funções são idênticas exceto por em que linha a visita fica. Essa única linha de diferença é a distinção inteira, e ela decide se um nó é tratado antes ou depois de as respostas dos filhos existirem.
// 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;
}Ele 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 childrenNomear as ordens pela posição é como elas costumam ser ensinadas, e não é o que as torna úteis. A distinção útil é se um nó é tratado antes ou depois de as respostas dos filhos existirem:
- Pré-ordem processa um nó sem saber nada das subárvores. Bom para copiar uma árvore, serializar, ou qualquer coisa em que os dados do próprio nó bastam.
- Em ordem numa árvore binária de busca produz saída ordenada. Isso não é coincidência — é a definição de uma BST expressa como um percurso.
- Pós-ordem processa um nó depois que os dois filhos terminaram. Qualquer resposta que combina resultados de baixo é pós-ordem, com ou sem esse nome. A parte 13 inteira é pós-ordem.
Custo: O(n) de tempo, O(h) de espaço para a pilha de chamadas, onde h é a altura.
Use quando — sempre. Este é o vocabulário em que o resto do trabalho com árvores é escrito.
Padrão 57 — Em ordem sem recursão
A parte 7 mostrou que o C# encerra o processo num stack overflow, sem chance de capturar, e que uma árvore degenerada é profunda. Então a versão iterativa importa mais aqui do que em outras linguagens.
As pessoas não conseguem reconstruir isso sob pressão porque tentam lembrar do código. O código sai de nomear o que a pilha guarda.
Escrever a pilha na mão só é difícil até você conseguir nomear o que está nela. Quando “esquerda pronta, ainda não visitado” é o invariante, o laço se escreve sozinho — e ele não pode estourar como a versão recursiva estoura numa árvore degenerada.
// 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;
}Ele 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 sortedA pilha guarda nós cuja subárvore esquerda terminou mas que ainda não foram visitados. É exatamente isso que a pilha de chamadas guardava implicitamente. Com essa frase na cabeça, o laço é forçado:
- Vá para a esquerda o máximo possível, empilhando tudo no caminho.
- Nada mais à esquerda? Desempilhe e visite — o lado esquerdo está pronto por construção.
- Depois vá para o filho direito, e volte ao passo 1.
A condição externa é cur is not null || st.Count > 0, e as duas metades são necessárias. A pilha pode estar vazia enquanto ainda existe uma subárvore direita para descer, que é o caso bem no começo e de novo no nó 4 do trace acima.
Custo: O(n) de tempo, O(h) de espaço — o mesmo espaço, mas no heap, onde ele não pode matar o processo.
Use quando a árvore pode ser profunda, ou quando o problema quer o percurso pausado e retomado — um iterador de BST é esse laço com o miolo tirado.
Padrão 58 — Percurso por níveis
Todo padrão até aqui foi em profundidade. O percurso por níveis é em largura, e é a mesma fila da parte 7 com uma adição.
O problema: uma fila é uma sequência plana e não sabe nada de níveis. Nós do nível 2 entram na fila enquanto o nível 1 ainda está sendo drenado, então tudo fica misturado.
Uma fila não sabe de níveis — ela é uma sequência plana. A fronteira é recuperada tirando uma foto de quantos nós estavam esperando no momento em que o nível começou.
// 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;
}Ele 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: 4O truque inteiro é int width = q.Count; antes do laço interno. Essa foto é quantos nós pertencem a este nível, e drenar exatamente essa quantidade acerta a fronteira.
Escreva for (int i = 0; i < q.Count; i++) no lugar e a condição é reavaliada a cada iteração contra uma fila que cresce conforme os filhos entram. O nível nunca acaba, e você recebe uma lista plana só — o trace acima mostra a contagem indo de 2 para 3 no meio do nível, que é exatamente o que daria errado.
Custo: O(n) de tempo, O(w) de espaço, onde w é o nível mais largo.
Use quando o problema menciona níveis, profundidade, ou o mais próximo. Profundidade mínima em particular deve ser BFS, não DFS — o BFS pode parar na primeira folha que encontra, enquanto o DFS tem que explorar tudo.
Padrão 59 — Zigzag, vistas laterais, e o resto
Uma vez que o percurso por níveis existe, um número surpreendente de problemas de árvore é uma linha em cima dele.
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;
}Ele 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.O zigzag é onde as pessoas se enrolam, porque o instinto é alternar o percurso — enfileirar direita antes de esquerda nos níveis ímpares, ou trocar a fila por uma pilha. Isso funciona, é chato de escrever, e é fácil de errar.
A ordem da fila não precisa mudar. Monte os níveis normalmente, depois inverta as linhas alternadas. Mesma resposta, uma linha, nada para depurar.
As vistas laterais são o último e o primeiro elemento de cada nível. A profundidade máxima é a contagem. O nível mais largo é um Max. Nenhum deles precisa de algoritmo próprio.
Use quando qualquer pergunta for formulada por nível. Monte os níveis, depois responda a pergunta sobre a lista.
Padrão 60 — Reconstruir uma árvore a partir de dois percursos
Dados o percurso em pré-ordem e o em ordem, reconstrua a árvore.
Um percurso sozinho nunca basta — muitas árvores diferentes compartilham a mesma pré-ordem. Dois, com o percurso em ordem entre eles, fixam a árvore exatamente.
Ache a posição da raiz no array em ordem com um dicionário, não com uma varredura. Uma varredura faz cada nível ser O(n) e a reconstrução inteira ser O(n²) numa árvore degenerada — que é exatamente a entrada que um teste vai usar.
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;
}Ele 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: TrueDuas coisas sustentam isso.
O primeiro valor não consumido da pré-ordem é sempre a próxima raiz. Um único cursor compartilhado anda para frente, e é por isso que Build(left) tem que ser chamado antes de Build(right) — a subárvore esquerda consome a parte dela da pré-ordem primeiro. Troque essas duas linhas e a árvore sai espelhada, sem nenhum erro.
O percurso em ordem diz onde dividir. Tudo à esquerda da posição da raiz pertence à subárvore esquerda, tudo à direita pertence à direita. O dicionário where faz esse lookup ser O(1); varrer o array em ordem no lugar disso faz a reconstrução inteira ser O(n²) numa árvore degenerada, que é precisamente a entrada que um caso de teste vai escolher.
Repare que o caso base lo > hi trata os intervalos vazios do trace — [0..-1] e [2..1] são como um filho ausente se anuncia.
Pós-ordem mais em ordem funciona do mesmo jeito, consumindo a pós-ordem de trás para frente e construindo a direita antes da esquerda. Pré-ordem mais pós-ordem não determina uma árvore de forma única.
Custo: O(n) de tempo e de espaço.
Use quando te derem dois percursos, ou quando estiver serializando e desserializando uma árvore.
O que lembrar
-
As três ordens diferem por uma linha. O que importa é se um nó é tratado antes ou depois de as respostas dos filhos existirem.
-
Em ordem numa BST sai ordenado. Essa é a definição, percorrida.
-
A pilha iterativa guarda “esquerda pronta, ainda não visitado”. Nomeie o invariante e o código sai; decorar o código não sobrevive à pressão.
-
Guarde
q.Countnuma variável local antes de drenar um nível. Reler isso na condição do laço significa que o nível nunca acaba. -
Não alterne o percurso para fazer zigzag. Monte os níveis, inverta as linhas alternadas.
-
Construa a subárvore esquerda antes da direita. Elas compartilham um cursor de pré-ordem, e a ordem dessas duas chamadas é toda a diferença entre uma árvore e o espelho dela.
-
Indexe o array em ordem com um dicionário. Varrer transforma O(n) em O(n²) exatamente na entrada que um teste vai escolher.
A parte 13 é o que você faz depois de conseguir chegar a todo nó: somas de caminho, diâmetro, ancestrais, e a distinção entre o que uma recursão retorna e o que ela carrega para baixo.