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
}
// 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}
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
}

Exercícios relacionados