Escreva uma função não-recursiva que verifique a existência de um valor negativo na árvore binária.
Passo 1
Este exercício pede uma função não-recursiva para detectar se existe algum valor negativo em uma árvore binária. O conteúdo da matéria envolve percorrimentos de árvore (tree traversal) e uso de estruturas auxiliares (pilha ou fila) para simular a recursão de forma iterativa.
Passo 2
Para evitar recursão, vamos usar uma pilha (stack) e fazer uma busca em profundidade (DFS). A pilha nos ajuda a armazenar os nós que ainda precisamos visitar, simulando as chamadas recursivas.
Passo 3
A ideia geral do algoritmo é: inicializar a pilha com a raiz (se ela não for nula); enquanto a pilha não estiver vazia, desempilhar um nó, verificar seu valor e, se for negativo, terminar retornando verdadeiro; caso contrário, empilhar seus filhos (direito e depois esquerdo) para continuar a busca.
Passo 4
Se esgotarmos todos os nós sem achar nenhum valor negativo, retornamos falso. A complexidade é O(n) no tempo (pois podemos visitar todos os nós) e O(n) no espaço no pior caso (altura da árvore).
Resposta
// Estrutura de nó da árvore binária
type Node struct {
value int
left *Node
right *Node
}
type Node struct {
value int
left *Node
right *Node
}
// Função não-recursiva que retorna true se houver valor negativo
func HasNegative(root *Node) bool {
if root == nil {
return false
}
// Pilha para simular a recursão
stack := []*Node{root}
func HasNegative(root *Node) bool {
if root == nil {
return false
}
// Pilha para simular a recursão
stack := []*Node{root}
for len(stack) > 0 {
// Desempilha o topo
n := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// Verifica valor negativo
if n.value < 0 {
return true
}
// Empilha filhos (direito primeiro para visitar esquerdos antes)
if n.right != nil {
stack = append(stack, n.right)
}
if n.left != nil {
stack = append(stack, n.left)
}
}
return false
}