Tehtäväsi on etsiä puussa oleva polku solmusta a solmuun b. Polku on puussa oleva reitti solmusta toiseen, joka kulkee solmujen välisiä yhteyksiä.
Esimerkiksi alla olevassa puussa polku solmusta 3 solmuun 2 on [3, 4, 1, 2] ja polku solmusta 1 solmuun 7 on [1, 4, 7].
Toteuta tiedostoon treepath.py funktio find_path, jolle annetaan parametrina viittaus puun juurisolmuun sekä solmujen tunnukset a ja b. Funktion tulee palauttaa polku listana tai None, jos polkua ei ole.
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 find_path(node, a, b):
# TODO
if __name__ == "__main__":
tree1 = Node(1, [Node(4, [Node(3), Node(7)]),
Node(5),
Node(2, [Node(6)])])
print(find_path(tree1, 3, 2)) # [3, 4, 1, 2]
print(find_path(tree1, 1, 7)) # [1, 4, 7]
print(find_path(tree1, 5, 5)) # [5]
print(find_path(tree1, 7, 3)) # [7, 4, 3]
print(find_path(tree1, 4, 8)) # None
tree2 = Node(1, [Node(2, [Node(3, [Node(4)])])])
print(find_path(tree2, 1, 4)) # [1, 2, 3, 4]
print(find_path(tree2, 4, 1)) # [4, 3, 2, 1]
print(find_path(tree2, 2, 3)) # [2, 3]
tree3 = Node(1, [Node(2), Node(3), Node(4)])
print(find_path(tree3, 2, 3)) # [2, 1, 3]
print(find_path(tree3, 1, 2)) # [1, 2]
print(find_path(tree3, 5, 5)) # None