Uma função recursiva sobre uma árvore costuma responder a uma pergunta menor do que a que o problema final faz. A altura de uma subárvore é um braço descendente que um pai pode estender. Um caminho máximo pode unir dois braços no pai em comum, mas essa forma unida não pode ser devolvida como um único braço. Mantenha esses dois significados separados.
Você vai começar somando apenas as folhas, depois vai ler uma visão pela direita por níveis em largura e encontrar uma chave por ranking com um percurso em ordem. As últimas tarefas contam somas-alvo descendentes e maximizam uma rota com sinal. Para o mapa de contagem de caminhos, registre apenas os ancestrais do ramo ativo e desfaça cada adição ao voltar. Estas árvores têm profundidade máxima de 300; sem esse limite, um percurso iterativo evita depender do limite da pilha de chamadas da linguagem.
A raiz pode unir os dois braços de seus filhos ao avaliar uma rota completa. Com os valores com sinal mostrados, essa rota soma seis. Se existisse um pai, ele só poderia estender um dos lados sem visitar a raiz duas vezes, então a raiz devolve quatro como seu melhor braço descendente. Um cálculo de altura faz a mesma distinção usando contagens de nós em vez de ganhos: cada filho tem altura um, e uni-los dá duas arestas passando pela raiz. A tarefa de saldos de folhas usa um significado de retorno totalmente diferente: soma dois e três e exclui o valor da raiz interna. Dê um nome ao valor de retorno antes de escrever a recorrência.