Deve devolver um array contendo todos os caminhos na árvore que vão dar ao valor mínimo que é possível encontrar na árvore. O tamanho do array deve ser igual ao número de vezes que o mínimo aparece na árvore, e os caminhos podem vir em qualquer ordem dentro do array (não precisa de se preocupar com a ordem).
Cada caminho é representando por uma string contendo uma sequência de caracteres 'E' e 'D' indicando como chegar ao nó correspondente quando se começa na raíz. Se o nó for a raíz, o caminho é simplesmente "R". A figura seguinte ilustra alguns caminhos possíveis para chegar ao nó a vermelho.
Armado com este conhecimento, pode agora compreender a figura seguinte, que ilustra algumas árvores t, e qual o array que o método ED240.paths(t) deve devolver, contendo os caminhos para todas as ocorrências do valor mínimo, indicadas nos nós a vermelho (note que a ordem dos caminhos não tem de ser esta):
É garantido que as árvores testadas com o seu programa são pequenas (100 nós no máximo), pelo que não tem de se preocupar (demasiado) com a eficiência.
Exemplo de Input/Output
Os exemplos correspondem às três árvores da figura.
| Árvore t em preorder | Exemplo de possível valor devolvido por ED240.paths(t) |
|---|---|
| 2 3 4 2 N N N 5 N 8 N N 2 6 N 2 N N 25 N N | ["R", "EEE", "D", "DED"] |
| 6 3 N 5 N 7 N N 10 8 N 9 N N 1 N N | ["DD"] |
| 5 5 5 N N 5 N N 5 N N | ["R","D","E","ED","EE"] |
Teste Prático de Estruturas de Dados (CC1007)
8 de Junho de 2020