0677 - Nivele Bin

Cerința

Considerăm un arbore binar cu n noduri în care fiecare nod este numerotat de la 1 la n și conține o valoare număr natural. În acest arbore rădăcina este considerată pe nivelul 0, descendenții direcți ai rădăcinii pe nivelul 1, etc. Să se determine numărul de nivele k din arbore și, pentru fiecare nivel i de la 0 la k, numărul de noduri situate pe acel nivel.

Date de intrare

Fișierul de intrare nivelebinin.txt conține pe prima linie numărul n. Fiecare dintre următoarele n linii conține câte 3 numere X st dr; linia i + 1 din fișier conține informațiile despre nodul numerotat cu i: X reprezintă valoare din nod, st reprezintă numărul de ordine al descendentului stâng sau 0 dacă nodul i nu are descendent stâng, iar dr reprezintă numărul de ordine al descendentului drept sau 0 dacă nodul i nu are descendent drept.

Date de ieșire

Fișierul de ieșire nivelebinout.txt va conține pe prima linie numărul k, iar pe a doua linie k+1 numere naturale separate prin exact un spațiu, al i-lea număr reprezentând numărul de noduri situate pe nivelul i-1 din arbore.

Restricții și precizări

• 1 ≤ n ≤ 1000
• valorile din nodurile arborelui vor fi mai mici sau egale cu 1.000.000

Exemplul 1

nivelebinin.txt

6

2 3 5

6 0 6

1 0 0

7 1 2

4 0 0

10 0 0

nivelebinout.txt

3

1 2 3

Exemplul 2

nivelebinin.txt

7

1 2 3

2 4 0

3 5 6

4 0 0

5 7 0

6 0 0

7 0 0

nivelebinout.txt

3

1 2 4

Rezolvare

#0677 - Nivele Bin
class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def read_tree_from_file(file):
    n = int(file.readline())
    if not (1 <= n <= 1000):
        return None

    nodes = [None]  # index 0 nu este folosit

    for i in range(1, n + 1):
        x, st, dr = map(int, file.readline().split())
        if not (1 <= x <= 1000000):
            return None
        if not (0 <= st <= n):
            return None
        if not (0 <= dr <= n):
            return None
        nodes.append(TreeNode(x, st, dr))

    return nodes

def calculate_levels_and_counts(root, nodes):
    levels_counts = {}
    stack = [(root, 0)]  # Stivă de noduri și niveluri

    while stack:
        node, level = stack.pop()

        if level not in levels_counts:
            levels_counts[level] = 1
        else:
            levels_counts[level] += 1

        if nodes[node].left:
            stack.append((nodes[node].left, level + 1))
        if nodes[node].right:
            stack.append((nodes[node].right, level + 1))

    return levels_counts

def check_restrictions(n):
    return 1 <= n <= 1000

def main():
    with open('nivelebinin.txt', 'r') as file:
        n = int(file.readline())
        if not check_restrictions(n):
            print("false")
            return

        nodes = read_tree_from_file(file)
        if nodes is None:
            print("false")
            return

        root = 1  # Rădăcina arborelui
        levels_counts = calculate_levels_and_counts(root, nodes)

        k = len(levels_counts) - 1  # Numărul de niveluri
        counts_list = [levels_counts[i] for i in range(k + 1)]

    with open('nivelebinout.txt', 'w') as file:
        file.write(str(k) + '\n')
        file.write(' '.join(map(str, counts_list)))

if __name__ == "__main__":
    main()

 Explicatie 

Exemplul corespunde arborelui de mai jos, în care au fost marcate cu albastru valorile din noduri, iar cu roșu numerele de ordine ale nodurilor.
Arborele conține trei nivele:

• nivelul 0 conține doar rădăcina, nodul numerotat cu 4
• nivelul 1 conține două noduri, cele numerotate cu 1 2
• nivelul 2 conține trei noduri, cele numerotate cu 3 5 6