Editing 0673 - Dif Sub

== 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. Să se determine diferența în valoare absolută a sumei valorilor memorate în subarborele stâng al rădăcinii și suma valorilor memorate în subarborele drept al rădăcinii.
== Date de intrare ==
Fișierul de intrare difsubin.txt conține pe prima linie numărul n. Fiecare dintre următoarele n linii contine câte 3 numere X st dr; linia i + 1 din fișier conține informatiile 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 difsubout.txt va conține pe prima linie numărul D, cu semnificația precizată.
== Restricții și precizări ==
*1 ≤ n ≤ 1000
*valorile din nodurile arborelui vor fi mai mici sau egale cu 1.000.000
== Exemplu 1 ==
; difsubin.txt
: 6
: 2 3 5
: 6 0 6
: 1 0 0
: 7 1 2
: 4 0 0
: 10 0 0
; difsubout.txt
: 9
== Exemplu 2 ==
; difsubin.txt
: 5
: 3 2 3
: 7 4 0
: 1 0 0
: 5 0 0
: 2 0 0
; difsubout.txt
: 11
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#0673 - Dif Sub
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 _ in range(n):
        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_subtree_sum(node, nodes):
    if node == 0:
        return 0
    return nodes[node].value + calculate_subtree_sum(nodes[node].left, nodes) + calculate_subtree_sum(nodes[node].right, nodes)

def calculate_difference(root, nodes):
    left_sum = calculate_subtree_sum(nodes[root].left, nodes)
    right_sum = calculate_subtree_sum(nodes[root].right, nodes)
    return abs(left_sum - right_sum)

def main():
    with open('difsubin.txt', 'r') as file:
        nodes = read_tree_from_file(file)

    if nodes is None:
        print("false")
        return

    root = 1  # Arborele începe de la rădăcină (nodul 1)
    difference = calculate_difference(root, nodes)

    with open('difsubout.txt', 'w') as file:
        file.write(str(difference))

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>
Suma valorilor nodurilor din subarborele stâng al rădăcinii este 7, iar suma valorilor nodurilor din subarborele drept al rădăcinii este 16. Diferența în valoare absolută a celor două valori este 9.