Escreva uma função que receba um nível da árvore e imprima todos os nós nesse nível.

Passo 1

O enunciado pede uma função que, dado um nível k de uma árvore binária, imprima todos os nós que estão exatamente nesse nível. O conteúdo que vamos usar envolve a travessia de árvores binárias por níveis, que pode ser feita de forma recursiva (descendo até o nível desejado) ou usando busca em largura (BFS) com fila.

Passo 2

Primeiro, definimos a estrutura básica de um nó de árvore binária em C++ para ilustrar:

Passo 3

Agora, usamos uma abordagem recursiva. A ideia é: se o nó atual for nulo, não faz nada; se k for 1, ele está no nível desejado e podemos imprimir seu valor; caso contrário, chamamos recursão nos filhos com k-1.
Em alternativa, podemos usar BFS com uma fila: inserimos a raiz e vamos consumindo nível a nível, decrementando um contador. Quando chegamos no nível k, imprimimos todos os nós na fila que pertencem a esse nível.

Passo 4

A complexidade da solução recursiva e da iterativa é O(n), pois visitamos cada nó no pior caso uma vez.

Resposta

// Definição de nó de árvore binária
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// Abordagem recursiva: imprime todos os nós no nível k (sendo a raiz nível 1)
void printLevel(TreeNode* root, int k) {
if (!root || k < 1) return; // Caso base: nó vazio ou nível inválido
if (k == 1) {
std::cout << root->val << " "; // Estamos no nível desejado
} else {
// Desce um nível em cada chamada recursiva
printLevel(root->left, k - 1);
printLevel(root->right, k - 1);
}
}
// Exemplo de uso:
// TreeNode* root = …; // constrói ou carrega a árvore
// int nivel = 3;
// printLevel(root, nivel);
// std::cout << std::endl;
// Abordagem iterativa (BFS):
#include <queue>
void printLevelBFS(TreeNode* root, int k) {
if (!root || k < 1) return;
std::queue<TreeNode*> q;
q.push(root);
int nivelAtual = 1;
while (!q.empty() && nivelAtual < k) {
int sz = q.size();
while (sz–) {
TreeNode* node = q.front(); q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
nivelAtual++;
}
// Agora a fila contém todos os nós do nível k
while (!q.empty()) {
std::cout << q.front()->val << " ";
q.pop();
}
std::cout << std::endl;
}

Exercícios relacionados