Привет, меня зовут Андрей, и сегодня я расскажу вам о задаче ″Обойди дерево″. Эта задача связана с марсианскими миссиями и генеалогическим древом кандидатов.
Когда-то, давным-давно, первый человек ступил на Марс. С тех пор прошло несколько поколений, и теперь перед каждой марсианской миссией стоит вопрос отбора претендентов. Одним из критериев отбора является ″марсианский семейный стаж″. Это время, которое провели на Марсе предки кандидата.
Например, у нас есть бинарное дерево, которое представляет генеалогическое древо кандидата. В каждом узле этого дерева содержится информация о предке⁚ его имя и значение space_experience ー опыт, который он провел на Марсе.Наша задача ⎼ написать метод, который будет обходить это дерево и возвращать сумму значений space_experience всех узлов.Я сделал это написав следующий код на языке программирования Python⁚
python
class TreeNode⁚
def __init__(self, name, space_experience)⁚
self.name name
self.space_experience space_experience
self.left None
self.right None
def sum_space_experience(root)⁚
if root is None⁚
return 0
sum_left sum_space_experience(root.left)
sum_right sum_space_experience(root.right)
return root.space_experience sum_left sum_right
# Создаем генеалогическое древо
root TreeNode(‘Andrey’, 5)
root.left TreeNode(‘Ivan’, 3)
root.right TreeNode(‘Maria’, 2)
root.left.left TreeNode(‘Alex’, 1)
root;left.right TreeNode(‘Tanya’, 2)
root.right.left TreeNode(‘Peter’, 4)
root.right.right TreeNode(‘Olga’, 2)
# Вычисляем сумму space_experience
sum_experience sum_space_experience(root)
print(″Сумма space_experience всех узлов дерева⁚″, sum_experience)
В данном коде, мы создаем класс TreeNode, который представляет узел дерева. Узлы содержат информацию о имени предка и значении space_experience. Узлы также имеют ссылки на левого и правого потомков.
Метод sum_space_experience принимает на вход корень дерева и рекурсивно обходит каждый узел. Если узел пустой, то возвращается 0. В противном случае, происходит рекурсивный вызов для левого и правого поддеревьев, и сумма их значений space_experience складывается с значением текущего узла. В конце метода возвращается общая сумма.
В результате выполнения кода, мы получим сумму всех значений space_experience всех узлов дерева.
Таким образом, я рассказал вам о задаче ″Обойди дерево″, которая связана с марсианскими миссиями и генеалогическим древом кандидатов.