Модуль: Деревья решений. Читаем и разбираем JSON


7. Путь к узлу

Дано дерево решений и id целевого узла. Найдите путь от корня (id=0) до этого узла.

Формат входных данных
Первая строка: JSON с деревом. Вторая строка: целевой id узла.

Формат выходных данных
ID узлов от корня до целевого, через пробел.
Примеры
№Входные данныеВыходные данные
1 {"nodes": [{"id": 0, "type": "decision", "feature_index": 1, "threshold": 0.4676, "left_child": 1, "right_child": 2}, {"id": 1, "type": "leaf", "class": 0}, {"id": 2, "type": "leaf", "class": 1}]}
2
 
0 2
Напишите программу
Auto
       

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python6
Комментарий учителя

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!
Разбор

💡 Полезно знать

  • Корень (id=0) не имеет родителя — это условие остановки
  • Путь всегда существует, если целевой узел есть в дереве
  • Длина пути = глубина целевого узла + 1
💡 Подсказка 1: Два подхода к решению ▶
Способ 1: Идти от корня вниз, запоминая путь (DFS)
Способ 2: Построить "обратные ссылки" (от ребёнка к родителю) и идти от целевого узла вверх к корню
Какой проще?
💡 Подсказка 2: Два подхода к решению ▶
В исходных данных каждый узел знает своих детей (left_child, right_child). Но нам нужно наоборот — чтобы ребёнок знал родителя.
  
родитель = {}  # словарь: id ребёнка → id родителя

для каждого узла в nodes:
    если узел — внутренний (decision):
        родитель[узел["left_child"]] = узел["id"]
        родитель[узел["right_child"]] = узел["id"]
Теперь родитель[5] скажет, кто является родителем узла 5.
💡 Подсказка 3: Восстановление пути ▶
Начни с целевого узла и поднимайся вверх, пока не дойдёшь до корня.
  
текущий = целевой_id

пока текущий есть в словаре родитель:
    текущий = родитель[текущий]
    добавить текущий в путь

перевернуть путь  # потому что собирали от листа к корню
💡 Подсказка 4: Альтернативный способ (DFS от корня) ▶
Можно искать путь рекурсивным обходом от корня.
  
функция найти_путь(текущий_id, цель, путь):
    если текущий_id == цель:
        вернуть путь + [текущий_id]  # Нашли!
    
    узел = словарь_узлов[текущий_id]
    
    если узел — лист:
        вернуть None  # Тупик, цели тут нет
    
    # Ищем в левом поддереве
    результат = найти_путь(узел["left_child"], цель, путь + [текущий_id])
    если результат не None:
        вернуть результат
    
    # Ищем в правом поддереве
    вернуть найти_путь(узел["right_child"], цель, путь + [текущий_id])

путь = найти_путь(0, целевой_id, [])
Обсуждения (0)
Загрузка...
Чтобы оставить комментарий, необходимо авторизоваться
💬
Пока нет комментариев. Будьте первым!
Решения (0)

Решения:

Нет доступных решений