Tehtäväsi on muodostaa lista, joka sisältää puun solmujen alipuiden koot pienimmästä suurimpaan.
Esimerkiksi alla olevassa puussa listan haluttu sisältö on [1, 1, 1, 1, 2, 3, 7]. Puussa on neljä lehteä, joissa alipuun koko on 1. Solmun 2 alipuun koko on 2, solmun 4 alipuun koko on 3 ja solmun 1 alipuun koko on 7.
Toteuta tiedostoon subtrees.py funktio count_subtrees, jolle annetaan parametrina viittaus puun juurisolmuun. Funktio palauttaa listana solmujen alipuiden koot.
class Node:
def __init__(self, value, children=None):
self.value = value
self.children = children if children else []
def __repr__(self):
if self.children == []:
return f"Node({self.value})"
else:
return f"Node({self.value}, {self.children})"
def count_subtrees(node):
# TODO
if __name__ == "__main__":
tree1 = Node(1, [Node(4, [Node(3), Node(7)]),
Node(5),
Node(2, [Node(6)])])
print(count_subtrees(tree1)) # [1, 1, 1, 1, 2, 3, 7]
tree2 = Node(1, [Node(2, [Node(3, [Node(4)])])])
print(count_subtrees(tree2)) # [1, 2, 3, 4]
tree3 = Node(1, [Node(2), Node(3), Node(4)])
print(count_subtrees(tree3)) # [1, 1, 1, 4]