- Problemas Clássicos com Árvores Binárias (sem DP em árvore)
Os problemas abaixo não envolvem programação dinâmica em árvore, que será abordada em módulos futuros. Tópicos como árvores AVL e rotações também serão vistos posteriormente.
36.1 Travessia por Nível
Método 1: Fila + tabela hash para níveis. Cada nó é armazenado na fila e seu nível é registrado em um mapa, possibilitando agrupar valores por nível.
Método 2 (recomendado): Usar um array fixo simulando fila, processando um nível por vez. Sem necessidade de hash, apenas baseado no tamanho da fila a cada iteração.
#include <iostream>
#include <vector>
#include <memory>
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
const int MAXN = 2001;
TreeNode* fila[MAXN];
int f, t; // frente e traseira
std::vector<std::vector<int>> nivelOrden(TreeNode* raiz) {
std::vector<std::vector<int>> ans;
if (!raiz) return ans;
f = t = 0;
fila[t++] = raiz;
while (f < t) {
int sz = t - f;
std::vector<int> nivel;
for (int i = 0; i < sz; ++i) {
TreeNode* cur = fila[f++];
nivel.push_back(cur->val);
if (cur->left) fila[t++] = cur->left;
if (cur->right) fila[t++] = cur->right;
}
ans.push_back(nivel);
}
return ans;
}
36.2 Travessia em Zigue-Zague
Utiliza o mesmo array de fila e uma variável booleana reverse para indicar a direção de leitura de cada nível. Na coleta, percorre-se a fila do início ao fim ou do fim ao início conforme a direção.
std::vector<std::vector<int>> zigueZague(TreeNode* raiz) {
std::vector<std::vector<int>> ans;
if (!raiz) return ans;
f = t = 0;
fila[t++] = raiz;
bool direitaEsquerda = false;
while (f < t) {
int sz = t - f;
std::vector<int> nivel(sz);
for (int i = 0; i < sz; ++i) {
TreeNode* cur = fila[f + (direitaEsquerda ? sz - 1 - i : i)];
nivel[i] = cur->val;
}
for (int i = 0; i < sz; ++i) {
TreeNode* cur = fila[f++];
if (cur->left) fila[t++] = cur->left;
if (cur->right) fila[t++] = cur->right;
}
ans.push_back(nivel);
direitaEsquerda = !direitaEsquerda;
}
return ans;
}
36.3 Largura Máxima Especial
Usa duas filas (nó e id). Cada nó recebe um id baseado no índice heap (filho esquerdo = 2*id, direito = 2*id+1). A largura de um nível é a diferença entre o maior e menor id + 1.
const int MAXN2 = 3001;
TreeNode* nq[MAXN2];
long long iq[MAXN2];
int larguraBinaria(TreeNode* raiz) {
if (!raiz) return 0;
int ans = 1;
f = t = 0;
nq[t] = raiz;
iq[t++] = 1;
while (f < t) {
int sz = t - f;
long long larg = iq[t - 1] - iq[f] + 1;
if (larg > ans) ans = larg;
for (int i = 0; i < sz; ++i) {
TreeNode* node = nq[f];
long long id = iq[f++];
if (node->left) { nq[t] = node->left; iq[t++] = id * 2; }
if (node->right) { nq[t] = node->right; iq[t++] = id * 2 + 1; }
}
}
return ans;
}
36.4 Profundidade Máxima e Mínima
int maxProfundidade(TreeNode* r) {
return r ? std::max(maxProfundidade(r->left), maxProfundidade(r->right)) + 1 : 0;
}
int minProfundidade(TreeNode* r) {
if (!r) return 0;
if (!r->left && !r->right) return 1;
int esq = r->left ? minProfundidade(r->left) : INT_MAX;
int dir = r->right ? minProfundidade(r->right) : INT_MAX;
return std::min(esq, dir) + 1;
}
36.5 Serialização e Desserialização Pré‑Ordem
Converte a árvore em string usando pré‑ordem, marcando nós nulos com '#'. A desserialização reconstrói a árvore a partir da string usando fila de tokens.
class Codec {
public:
std::string serializar(TreeNode* r) {
std::ostringstream oss;
auxSerial(r, oss);
return oss.str();
}
TreeNode* desserializar(std::string data) {
std::istringstream iss(data);
std::vector<std::string> tokens;
std::string token;
while (std::getline(iss, token, ',')) tokens.push_back(token);
int idx = 0;
return auxDeserial(tokens, idx);
}
private:
void auxSerial(TreeNode* r, std::ostringstream& oss) {
if (!r) { oss << "#,"; return; }
oss << r->val << ",";
auxSerial(r->left, oss);
auxSerial(r->right, oss);
}
TreeNode* auxDeserial(const std::vector<std::string>& tokens, int& i) {
if (tokens[i] == "#") { ++i; return nullptr; }
TreeNode* no = new TreeNode(std::stoi(tokens[i++]));
no->left = auxDeserial(tokens, i);
no->right = auxDeserial(tokens, i);
return no;
}
};
36.6 Serialização por Nível
Semelhante à anterior, mas a ordem de visita é BFS. Usa fila de nós para gerar a string e, na desserialização, constrói nós na mesma ordem.
36.7 Construção a partir de Pré‑Ordem e In‑Ordem
Usa mapa para indexar valores da in‑ordem. O primeiro da pré‑ordem é a raiz; recursivamente divide os intervalos.
TreeNode* construir(const std::vector<int>& pre, const std::vector<int>& in) {
if (pre.empty() || pre.size() != in.size()) return nullptr;
std::unordered_map<int, int> map;
for (int i = 0; i < in.size(); ++i) map[in[i]] = i;
return aux(pre, 0, pre.size() - 1, in, 0, in.size() - 1, map);
}
TreeNode* aux(const std::vector<int>& pre, int l1, int r1,
const std::vector<int>& in, int l2, int r2,
const std::unordered_map<int, int>& map) {
if (l1 > r1) return nullptr;
TreeNode* raiz = new TreeNode(pre[l1]);
int k = map.at(pre[l1]);
raiz->left = aux(pre, l1 + 1, l1 + k - l2, in, l2, k - 1, map);
raiz->right = aux(pre, l1 + k - l2 + 1, r1, in, k + 1, r2, map);
return raiz;
}
36.8 Verificar Árvore Binária Completa
BFS: após encontrar um nó com filho esquerdo ausente ou incompleto, todos os nós seguintes devem ser folhas.
36.9 Contagem de Nós em Árvore Completa (O(log² n))
Compara a altura do caminho mais à esquerda da subárvore direita com a altura total para decidir se a subárvore esquerda é completa.
36.10 LCA em Árvore Binária Comum
TreeNode* lca(TreeNode* r, TreeNode* p, TreeNode* q) {
if (!r || r == p || r == q) return r;
auto esq = lca(r->left, p, q);
auto dir = lca(r->right, p, q);
if (esq && dir) return r;
return esq ? esq : dir;
}
36.11 LCA em BST
TreeNode* lcaBST(TreeNode* r, TreeNode* p, TreeNode* q) {
while (true) {
if (r->val > std::max(p->val, q->val)) r = r->left;
else if (r->val < std::min(p->val, q->val)) r = r->right;
else return r;
}
}
36.12 Caminhos com Soma Igual a target
void buscaCaminhos(TreeNode* cur, int alvo, int soma, std::vector<int>& path, std::vector<std::vector<int>>& ans) {
if (!cur->left && !cur->right) {
if (cur->val + soma == alvo) {
path.push_back(cur->val);
ans.push_back(path);
path.pop_back();
}
return;
}
path.push_back(cur->val);
if (cur->left) buscaCaminhos(cur->left, alvo, soma + cur->val, path, ans);
if (cur->right) buscaCaminhos(cur->right, alvo, soma + cur->val, path, ans);
path.pop_back();
}
36.13 Verificar Árvore Balanceada
Pós‑ordem com flag global ou retornando altura; se desbalanceada, retorna -1.
36.14 Verificar BST
In‑ordem iterativa com auxílio de pilha ou recursão retornando min/max.
36.15 Podar BST
Remove nós fora do intervalo [low, high] recursivamente.
36.16 Roubo em Árvore Binária (House Robber)
Para cada nó, retorna dois valores: roubando aquele nó (soma com netos) ou não roubando (soma dos filhos).
- Padrões de Recursão Clássicos
38.1 Subsequências de String (sem duplicatas)
Duas versões: uma com string path e outra com array de char e índice de tamanho. Usa set para garantir unicidade.
38.2 Subconjuntos de Array com Duplicatas
Ordena o array e, para cada grupo de valores iguais, decide quantos incluir (0 até a contagem do grupo).
38.3 Permutações sem Duplicatas
Troca recursiva de elementos, sem verificação de repetição (todos distintos).
38.4 Permutações com Duplicatas
Usa set local para evitar trocar o mesmo valor para a posição i mais de uma vez.
38.5 Inverter Pilha com Recursão
void inverterPilha(std::stack<int>& s) {
if (s.empty()) return;
int fundo = removerFundo(s);
inverterPilha(s);
s.push(fundo);
}
int removerFundo(std::stack<int>& s) {
int topo = s.top(); s.pop();
if (s.empty()) return topo;
int fundo = removerFundo(s);
s.push(topo);
return fundo;
}
38.6 Ordenar Pilha com Recursão
Funções auxiliares que operam sobre uma profundidade da pilha: obtém máximo, conta ocorrências e move os máximos para o fundo. Repete até ordenar.
38.7 Torres de Hanói
void hanoi(int n, const std::string& from, const std::string& to, const std::string& aux) {
if (n == 1) { std::cout << "Mover disco 1 de " << from << " para " << to << "\n"; return; }
hanoi(n-1, from, aux, to);
std::cout << "Mover disco " << n << " de " << from << " para " << to << "\n";
hanoi(n-1, aux, to, from);
}
- Recursão para Problemas Aninhados
Padrão: função recursiva processa substring a partir de i, retorna resultado e atualiza variável global where.
39.1 Avaliador de Expressão com Parênteses
Usa pilha de números e operadores, tratando multiplicação e divisão imediatamente. Subexpressões entre parênteses são avaliadas recursivamente.
39.2 Decodificar String Aninhada (ex: "3[a2[c]]")
Concatena tokens alfabéticos, repete quando encontra número antes de '[' e chama recursão para o conteúdo.
39.3 Contagem de Átomos (Fórmula Molecular)
Similar, retorna um map com contagens, lidando com parênteses e multiplicadores.
- Problema das N Rainhas
40.1 Versão Clássica com Array
Armazena coluna de cada rainha em path[linha]. Verifica ataques na diagonal e coluna.
40.2 Versão com Bits
Usa inteiros para coluna, diagonal esquerda e direita. Gera candidatos a partir de ~(col|left|right) & limit.
- Máximo Divisor Comum e Princípio de Congruência
41.1 GCD e LCM
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
41.2 Número Mágico (n-ésimo múltiplo de a ou b)
Busca binária no intervalo. Contagem = m/a + m/b - m/lcm(a,b).
41.3 Congruência
Operações de adição, subtração e multiplicação podem ser feitas módulo m. Subtração: (a - b + m) % m.
- Técnica de Tabela e Observação de Padrões
42.1 Sacos de Maçã (8 e 6)
Para n par ≥ 18, resposta = (n-18)/8 + 3. Para valores menores, tabela fixa.
42.2 Jogo de Comer Grama
Se n % 5 == 0 ou 2, vence B; senão, vence A.
42.3 Soma de Inteiros Consecutivos
Um número pode ser escrito como soma de consecutivos se e somente se não for potência de 2.
42.4 String Boa (apenas um palíndromo de tamanho ≥ 2)
Para n ≥ 2, fórmula fechada: f(2)=3, f(3)=18, para n≥4: f(n) = 6*(n+1) % mod.
- Adivinhar Solução com Base no Tamanho dos Dados
Regra: 10⁷ a 10⁸ operações em 1 segundo. Escolha algoritmo apropriado (ex: O(n!) para n≤10, O(n·2^n) para n≤20, etc.).
43.1 Habilidade ideal (n ≤ 10)
Enumerar todas as permutações de habilidades para maximizar dano.
43.2 Super Palíndromos (10¹⁸)
Gerar raízes palindrômicas e verificar quadrados; apenas 86 casos no intervalo.
- Trie (Árvore de Prefixos)
44.1 Implementação com Nós Dinâmicos
class Trie {
struct Node {
int pass = 0, end = 0;
Node* next[26] = {};
} *root;
public:
Trie() { root = new Node(); }
void inserir(const std::string& w) {
Node* cur = root;
cur->pass++;
for (char c : w) {
int idx = c - 'a';
if (!cur->next[idx]) cur->next[idx] = new Node();
cur = cur->next[idx];
cur->pass++;
}
cur->end++;
}
int contar(const std::string& w) {
Node* cur = root;
for (char c : w) {
int idx = c - 'a';
if (!cur->next[idx]) return 0;
cur = cur->next[idx];
}
return cur->end;
}
int prefixo(const std::string& p) {
Node* cur = root;
for (char c : p) {
int idx = c - 'a';
if (!cur->next[idx]) return 0;
cur = cur->next[idx];
}
return cur->pass;
}
void remover(const std::string& w) {
if (contar(w) == 0) return;
Node* cur = root;
cur->pass--;
for (char c : w) {
int idx = c - 'a';
if (--cur->next[idx]->pass == 0) {
delete cur->next[idx];
cur->next[idx] = nullptr;
return;
}
cur = cur->next[idx];
}
cur->end--;
}
};
44.2 Implementação com Array Estático
Usa três arrays globais: tree[MAXN][26], end[MAXN], pass[MAXN]. cnt = 1 (raiz). Operações idênticas.
Fenwick Tree (BIT) — Exemplo Final
class BIT {
int n;
std::vector<int> bit;
public:
BIT(int _n) : n(_n), bit(_n+1) {}
int query(int x) {
int s = 0;
while (x > 0) { s += bit[x]; x -= x & -x; }
return s;
}
void add(int x) {
while (x <= n) { bit[x]++; x += x & -x; }
}
};