Faça um algoritmo para somar os nós presentes nos níveis impares de uma árvore binária
Passo 1
O objetivo é criar um procedimento que receba a raiz de uma árvore binária e some apenas os valores dos nós que estão em níveis ímpares. Esse problema envolve travessia de árvore (DFS ou BFS) e controle do nível de cada nó.
Passo 2
Uma forma simples é usar uma DFS recursiva, passando junto um parâmetro que indica se o nível atual é ímpar ou par. Dessa forma, a cada chamada posso alternar esse indicador e decidir se somo ou não o valor do nó.
Passo 3
Na recursão, primeiro trato o caso base (nó nulo retorna zero). Depois, se o indicador mostrar que estou em nível ímpar, incluo o valor do nó na soma. Em seguida faço chamada recursiva para os filhos trocando o indicador de paridade.
Passo 4
Agora que entendemos a estratégia, podemos escrever um pseudocódigo claro usando um parâmetro booleano chamado isImpar, que vale verdadeiro quando estamos em nível ímpar.
Resposta
Algoritmo SomaNiveisImpares(no, isImpar):
se no == nulo então
retorne 0
fim se
soma ← 0
se isImpar então
soma ← soma + no.valor
fim se
soma ← soma + SomaNiveisImpares(no.esquerda, ¬isImpar)
soma ← soma + SomaNiveisImpares(no.direita, ¬isImpar)
retorne soma
se no == nulo então
retorne 0
fim se
soma ← 0
se isImpar então
soma ← soma + no.valor
fim se
soma ← soma + SomaNiveisImpares(no.esquerda, ¬isImpar)
soma ← soma + SomaNiveisImpares(no.direita, ¬isImpar)
retorne soma
Chamada inicial:
SomaNiveisImpares(raiz, verdadeiro) // considera raiz no nível 1 (ímpar)
SomaNiveisImpares(raiz, verdadeiro) // considera raiz no nível 1 (ímpar)