Em uma árvore binária, faça um algoritmo para alterar o valor de cada nó (exceto nó folha) para a soma dos valores dos nós esquerda e direita.
Passo 1
O enunciado pede para alterar o valor de cada nó interno (não-folha) de uma árvore binária de modo que passe a ser a soma dos valores de seus filhos esquerdo e direito. O conteúdo envolvido é Árvores Binárias e Recursão, e vamos precisar fazer um percurso em pós-ordem para processar primeiro os filhos antes de atualizar o nó pai.
Passo 2
Para não perdermos o valor original dos filhos (que serão usados na soma), nossa função recursiva deve retornar o valor antiga do nó antes da atualização. Assim, ao subirmos na recursão, o pai recebe exatamente o valor original que o filho tinha.
A lógica central é: se o nó for nulo, retornamos 0 (ou ignoramos); se for folha, retornamos seu valor sem alterar; caso contrário, chamamos recursivamente para o filho esquerdo e direito, guardamos os valores retornados (originais), atualizamos o nó atual com essa soma e então retornamos o valor original do nó para quem o chamou.
A lógica central é: se o nó for nulo, retornamos 0 (ou ignoramos); se for folha, retornamos seu valor sem alterar; caso contrário, chamamos recursivamente para o filho esquerdo e direito, guardamos os valores retornados (originais), atualizamos o nó atual com essa soma e então retornamos o valor original do nó para quem o chamou.
Passo 3
Segue o pseudocódigo do algoritmo em estilo recursivo:
função atualizarValor(nó):
se nó == nulo:
retornar 0
se nó.esquerda == nulo e nó.direita == nulo: // caso folha
retornar nó.valor
valorOriginal ← nó.valor
somaEsquerda ← atualizarValor(nó.esquerda)
somaDireita ← atualizarValor(nó.direita)
nó.valor ← somaEsquerda + somaDireita
retornar valorOriginal
função atualizarValor(nó):
se nó == nulo:
retornar 0
se nó.esquerda == nulo e nó.direita == nulo: // caso folha
retornar nó.valor
valorOriginal ← nó.valor
somaEsquerda ← atualizarValor(nó.esquerda)
somaDireita ← atualizarValor(nó.direita)
nó.valor ← somaEsquerda + somaDireita
retornar valorOriginal
Resposta
A função atualizarValor deve ser chamada passando a raiz da árvore para que, em pós-ordem, cada nó interno receba a soma dos valores originais de seus filhos.