Cerința

Se consideră un arbore binar în care nodurile memorează numere naturale nenule. Să se determine câte noduri din arbore au un singur descendent direct.

Date de intrare

Fișierul de intrare nrnod.in conține pe prima linie lista valorilor memorate în nodurile arborelui, obținute în urma parcurgerii în preordine (rădăcină, stâng, drept). Dacă un nod nu are descendent stâng, în listă va apare valoarea 0. Dacă un nod nu are descendent drept, în listă va apare valoarea 0.

Date de ieșire

Fișierul de ieșire nrnod.out va conține pe prima linie un singur număr C, reprezentând numărul de noduri din arbore care au un singur descendent direct.

Restricții și precizări

• se recomandă folosirea arborilor alocați dinamic.

Exemplu

nrnod.in

67 51 18 0 0 24 0 0 48 0 11 0 0

nrnod.out

1

Explicație

Exemplul corespunde arborelui desenat mai jos:

Nodul din arbore care are un singur descendent direct este cel cu valoarea 48.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("nrnod.in");
ofstream cout("nrnod.out");

int n, c;
bool ok = false;

void citire(int nod, int val){
    int x;
    cin >> x;
    if(nod % 2 == 0){
        if(x == 0)
            ok = true;
        else
            ok = false;
    }
    else{
        if((x != 0 && ok) || (x==0 && !ok)){
            ok = false;
            c++;
        }
        else{
            ok = false;
        }
    }
    if(x){
        citire(nod * 2, x);
        citire(nod * 2 + 1, x);
    }
}

int main(){
    citire(1, 0);
    cout << c;
    return 0;
}