Diferença Mínima Absoluta em uma Árvore de Busca Binária (BST)
Dada a raiz de uma Árvore de Busca Binária (BST), retorne a menor diferença absoluta entre os valores de quaisquer dois nós distintos na árvore. A diferença absoluta é definida como o valor positivo resultante da subtração entre dois valores.
Um conceito fundamental ao lidar com BSTs é que uma travessia em ordem (in-order traversal) produz uma sequência de valores ordenada. Isso transforma problemas de otimização ou busca de diferenças em uma BST em problemas análogos em um array ordenado, simplificando a abordagem.
Abordagem 1: Coletar valores e calcular
A ideia mais direta é realizar uma travessia em ordem na BST para coletar todos os valores dos nós em um vetor. Uma vez que o vetor está preenchido e ordenado (devido às propriedades da BST e da travessia em ordem), a menor diferença pode ser encontrada comparando elementos adjacentes.
/**
* Definição para um nó de árvore binária.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solucao {
private:
std::vector<int> valoresOrdenados; // Vetor para armazenar os valores em ordem
void percorrerEmOrdem(TreeNode* noAtual) {
if (noAtual == nullptr) {
return;
}
percorrerEmOrdem(noAtual->left); // Visita a subárvore esquerda
valoresOrdenados.push_back(noAtual->val); // Adiciona o valor do nó atual
percorrerEmOrdem(noAtual->right); // Visita a subárvore direita
}
public:
int obterDiferencaMinima(TreeNode* raiz) {
valoresOrdenados.clear(); // Garante que o vetor esteja vazio para cada chamada
percorrerEmOrdem(raiz); // Preenche o vetor com os valores ordenados
if (valoresOrdenados.size() < 2) {
return 0; // Se houver menos de dois nós, a diferença não é aplicável
}
int diferencaMinima = INT_MAX; // Inicializa com o maior valor possível
for (size_t i = 1; i < valoresOrdenados.size(); ++i) {
// Calcula a diferença entre elementos adjacentes e atualiza o mínimo
diferencaMinima = std::min(diferencaMinima, valoresOrdenados[i] - valoresOrdenados[i-1]);
}
return diferencaMinima;
}
};
Abordagem 2: Travessia em ordem com ponteiros
É possível calcular a diferença mínima em uma única travessia em ordem, mantendo um ponteiro para o nó anterior visitado. Durante a travessia, quando um nó é visitado, comparamos seu valor com o valor do nó anterior (se existir) e atualizamos a diferença mínima global. Este método evita o uso de um vetor extra, otimizando o espaço.
/**
* Definição para um nó de árvore binária.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solucao {
public:
int menorDiferenca = INT_MAX; // Variável para armazenar a menor diferença encontrada
TreeNode* noAnterior = nullptr; // Ponteiro para o nó visitado anteriormente na travessia em ordem
void calcularDiferenca(TreeNode* noAtual) {
if (noAtual == nullptr) {
return;
}
calcularDiferenca(noAtual->left); // Visita a subárvore esquerda
if (noAnterior != nullptr) {
// Se há um nó anterior, calcula a diferença e atualiza o mínimo
menorDiferenca = std::min(menorDiferenca, noAtual->val - noAnterior->val);
}
noAnterior = noAtual; // Atualiza o nó anterior para o nó atual
calcularDiferenca(noAtual->right); // Visita a subárvore direita
}
int obterDiferencaMinima(TreeNode* raiz) {
calcularDiferenca(raiz);
return menorDiferenca;
}
};
Abordagem 3: Iterativa com Pilha
A travessia em ordem também pode ser implementada iterativamente usando uma pilha. Esta abordagem simula o comportamento recursivo, visitando primeiro os nós mais à esquerda, depois o nó atual, e por fim os nós à direita. A lógica de manter um nó anterior para calcular a diferença mínima permanece a mesma.
/**
* Definição para um nó de árvore binária.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solucao {
public:
int obterDiferencaMinima(TreeNode* raiz) {
std::stack<TreeNode*> pilha;
TreeNode* noAtual = raiz;
TreeNode* noAnterior = nullptr;
int menorDiferenca = INT_MAX;
while (noAtual != nullptr || !pilha.empty()) {
if (noAtual != nullptr) {
// Percorre para a esquerda, empilhando os nós
pilha.push(noAtual);
noAtual = noAtual->left;
} else {
// Chegou ao nó mais à esquerda, desempilha e processa
noAtual = pilha.top();
pilha.pop();
if (noAnterior != nullptr) {
// Se existe um nó anterior, calcula a diferença
menorDiferenca = std::min(menorDiferenca, noAtual->val - noAnterior->val);
}
noAnterior = noAtual; // Atualiza o nó anterior
noAtual = noAtual->right; // Move para a subárvore direita
}
}
return menorDiferenca;
}
};
Modos em uma Árvore de Busca Binária (BST)
Dada a raiz de uma Árvore de Busca Binária (BST) que pode conter valores duplicados, encontre e retorne todos os modos (elementos com a maior frequência de ocorrência). Se houver vários modos, eles podem ser retornados em qualquer ordem. A definição de BST aqui permite que valores no filho esquerdo sejam menores ou iguais ao nó pai, e valores no filho direito sejam maiores ou iguais ao nó pai.
Abordagem 1: Mapear frequências e ordenar
Uma solução genérica para qualquer árvore binária seria realizar uma travessia completa, usar um mapa para contar a frequência de cada elemento, e então processar o mapa para encontrar os elementos com a frequência máxima. Isso envolve copiar os pares (elemento, frequência) para um vetor e ordená-lo por frequência, ou iterar para encontrar a frequência máxima e depois coletar os modos.
/**
* Definição para um nó de árvore binária.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solucao {
public:
std::unordered_map<int, int> contagemFrequencias; // Mapa: valor -> frequência
std::vector<int> modosEncontrados;
void contarFrequencias(TreeNode* noAtual) {
if (noAtual == nullptr) {
return;
}
contarFrequencias(noAtual->left);
contagemFrequencias[noAtual->val]++; // Incrementa a frequência do valor atual
contarFrequencias(noAtual->right);
}
// Função de comparação estática para ordenar pares por frequência decrescente
static bool compararPares(const std::pair<int, int>& a, const std::pair<int, int>& b) {
return a.second > b.second; // Ordena do mais frequente para o menos frequente
}
std::vector<int> encontrarModos(TreeNode* raiz) {
if (raiz == nullptr) {
return modosEncontrados;
}
contarFrequencias(raiz); // Preenche o mapa de frequências
// Converte o mapa em um vetor de pares para possibilitar a ordenação
std::vector<std::pair<int, int>> paresFrequencia(contagemFrequencias.begin(), contagemFrequencias.end());
// Ordena o vetor de pares com base na frequência
std::sort(paresFrequencia.begin(), paresFrequencia.end(), compararPares);
if (paresFrequencia.empty()) { // Verifica se há elementos após ordenar
return modosEncontrados;
}
modosEncontrados.push_back(paresFrequencia[0].first); // Adiciona o primeiro modo (o mais frequente)
for (size_t i = 1; i < paresFrequencia.size(); ++i) {
// Adiciona outros modos que tenham a mesma frequência máxima
if (paresFrequencia[i].second == paresFrequencia[0].second) {
modosEncontrados.push_back(paresFrequencia[i].first);
} else {
break; // Se a frequência for menor, não há mais modos com a frequência máxima
}
}
return modosEncontrados;
}
};
Abordagem 2: Travessia em ordem em uma única passada
Dada a propriedade de BSTs (travessia em ordem produz uma sequência ordenada), podemos encontrar os modos em uma única travessia. Isso é possível mantendo o controle do nó anterior, da contagem de ocorrências do valor atual, e da frequência máxima observada até agora. Conforme percorremos a árvore, atualizamos a contagem do valor atual e ajustamos a lista de modos se uma nova frequência máxima for encontrada ou se a frequência atual for igual à máxima.
/**
* Definição para um nó de árvore binária.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solucao {
public:
std::vector<int> modosEncontrados;
int frequenciaMaxima = 0; // Armazena a maior frequência de ocorrência
int contagemAtual = 0; // Contagem da frequência do valor do nó atual
TreeNode* noAnterior = nullptr; // Ponteiro para o nó processado anteriormente na travessia
void encontrarModos(TreeNode* noAtual) {
if (noAtual == nullptr) {
return;
}
encontrarModos(noAtual->left); // Visita a subárvore esquerda
// Lógica de processamento do nó atual
if (noAnterior == nullptr || noAnterior->val != noAtual->val) {
contagemAtual = 1; // Novo valor, reinicia a contagem
} else {
contagemAtual++; // Mesmo valor que o anterior, incrementa a contagem
}
if (contagemAtual > frequenciaMaxima) {
frequenciaMaxima = contagemAtual; // Atualiza a frequência máxima
modosEncontrados.clear(); // Limpa modos antigos, pois encontramos uma frequência maior
modosEncontrados.push_back(noAtual->val); // Adiciona o novo modo
} else if (contagemAtual == frequenciaMaxima) {
modosEncontrados.push_back(noAtual->val); // Adiciona o modo se a frequência é igual à máxima
}
noAnterior = noAtual; // Atualiza o nó anterior para o nó atual
encontrarModos(noAtual->right); // Visita a subárvore direita
}
std::vector<int> findMode(TreeNode* raiz) {
encontrarModos(raiz);
return modosEncontrados;
}
};
Ancestral Comum Mais Baixo (LCA) em uma Árvore Binária
Dado um nó raiz de uma árvore binária e dois nós específicos, p e q, encontre o ancestral comum mais baixo (LCA) desses dois nós. O LCA é definido como o nó X que é ancestral tanto de p quanto de q, e tem a maior profundidade possível. Um nó pode ser seu próprio ancestral.
Encontrar o LCA geralmente envolve uma travessia de baixo para cima (post-order traversal) na árvore. A ideia é que, ao visitar um nó, você verifica se seus filhos esquerdo e direito contêm p ou q. Se ambos os lados retornam um nó (significando que um filho encontrou p e o outro encontrou q), então o nó atual é o LCA. Se apenas um lado retorna um nó, esse nó retornado é o LCA (ou um dos nós p/q, se eles são acnestrais um do outro).
/**
* Definição para um nó de árvore binária.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solucao {
public:
TreeNode* buscarLCA(TreeNode* raiz, TreeNode* nodeP, TreeNode* nodeQ) {
// Casos base para a recursão:
// 1. Se a raiz é nula, não há LCA.
// 2. Se a raiz é um dos nós procurados (p ou q), a raiz é o LCA (ou um deles).
if (raiz == nullptr || raiz == nodeP || raiz == nodeQ) {
return raiz;
}
// Busca LCA na subárvore esquerda
TreeNode* ancestralEsquerdo = buscarLCA(raiz->left, nodeP, nodeQ);
// Busca LCA na subárvore direita
TreeNode* ancestralDireito = buscarLCA(raiz->right, nodeP, nodeQ);
// Se ambos os ancestrais foram encontrados (um em cada subárvore),
// então o nó atual (raiz) é o LCA.
if (ancestralEsquerdo != nullptr && ancestralDireito != nullptr) {
return raiz;
}
// Se apenas um ancestral foi encontrado (na subárvore esquerda),
// significa que p e q estão ambos na subárvore esquerda, ou p (ou q) é o ancestral de q (ou p)
// e ambos estão na subárvore esquerda. Neste caso, o LCA está na esquerda.
else if (ancestralEsquerdo != nullptr) {
return ancestralEsquerdo;
}
// Analogamente, se apenas um ancestral foi encontrado na subárvore direita,
// o LCA está na direita.
else if (ancestralDireito != nullptr) {
return ancestralDireito;
}
// Se nenhum ancestral foi encontrado em ambas as subárvores,
// p e q não estão nesta subárvore.
else {
return nullptr;
}
}
TreeNode* lowestCommonAncestor(TreeNode* raiz, TreeNode* p, TreeNode* q) {
return buscarLCA(raiz, p, q);
}
};