Editing 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
<br>
== 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
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#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()

</syntaxhighlight>

== 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.
<br>
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