A árvore binária é completa?
É-lhe pedido que determine se a árvore binária fornecida é completa.
Uma árvore binária é completa se todos os níveis da árvore estiverem totalmente preenchidos, exceto o nível mais baixo, cujos nós são ocupados o mais à esquerda possível.
Ambas as árvores apresentadas abaixo são árvores binárias completas.
Entrada
A entrada contém inteiros separados por espaço que representam os valores nos nós da árvore binária. A ordem dos valores é fornecida conforme descrito na declaração anterior (percorrendo sempre da subárvore esquerda para a direita). Um valor de 0 significa que o nó não existe. É garantido que a árvore binária de entrada é válida.
Saída
O programa deve imprimir
Yes se a árvore binária for completa, e No caso contrário.Exemplos
Entrada | Saída |
1 2 3 4 5 8 9 0 0 0 0 0 0 6 7 0 0 0 0 | Yes |
1 2 3 4 5 8 0 0 0 0 0 6 7 0 0 0 0 | Yes |
1 2 3 4 5 0 0 0 0 6 7 0 0 8 9 0 0 0 0 | No |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | No |
Explicação
- O Exemplo 1 é uma árvore binária completa, pois o último nível está preenchido da esquerda para a direita
- O Exemplo 2 é uma árvore binária completa, pois o último nível está preenchido da esquerda para a direita
- O Exemplo 3 não é uma árvore binária completa, pois não se encontra preenchido completamente a partir da esquerda
.png?table=block&id=18a2c681-664d-812b-a5fa-d78610ca741b&cache=v2)
- O Exemplo 4 não é uma árvore binária completa, pois não se encontra preenchido completamente a partir da esquerda
.png?table=block&id=18a2c681-664d-8175-8e22-d634d394a41b&cache=v2)
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB