0756 - Nr Nod

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 nrnodin.txt 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 apărea valoarea 0. Dacă un nod nu are descendent drept, în listă va apărea valoarea 0.

Date de ieșire

Fișierul de ieșire nrnodout.txt 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.

Exemplul 1

nrnodin.txt

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

nrnodout.txt

Datele de intrare corespund restrictiilor impuse
1

Exemplul 2

nrnodin.txt

1000001 2 3 4 5 6 7 8 9 10

nrnodout.txt

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def build_tree(values):
    value = next(values)
    if value == 0:
        return None
    node = Node(value)
    node.left = build_tree(values)
    node.right = build_tree(values)
    return node


def count_single_child_nodes(node):
    if node is None:
        return 0
    count = count_single_child_nodes(node.left) + count_single_child_nodes(node.right)
    if (node.left is not None and node.right is None) or (node.left is None and node.right is not None):
        count += 1
    return count


def main():
    with open('nrnodin.txt', 'r') as fin:
        values = map(int, fin.readline().split())
    root = build_tree(iter(values))
    count = count_single_child_nodes(root)
    with open('nrnodout.txt', 'w') as fout:
        fout.write(str(count))
        if not all(1 <= value <= 1000000 for value in values if value != 0):
            print("Datele de intrare nu corespund restrictiilor impuse")
            return
        print("Datele de intrare corespund restrictiilor impuse")


if __name__ == "__main__":
    main()