Как узнать, существует ли путь на данном дереве?

Question

Я хочу реализовать функцию примерно так:

def is_path(t, path):
    """Return whether a given path exists in a tree, beginning
    at the root.
    >>> t = tree(1, [
             tree(2, [tree(4), tree(5)]),
             tree(3, [tree(6), tree(7)])
          ])
    >>> is_path(t, [1, 2])
    True
    >>> is_path(t, [1, 2, 4])
    True
    >>> is_path(t, [2, 4])
    False
    """
    if _______________________________:
    return False
    if _______________________________:
        return True
    return any([____________________________________________________________])

Вспомогательные функции:

метка (дерево) -> значение дерева

ветви (дерево) -> список ветвей (также деревьев)

1010 *, например *

    1
   / \
  2   3

метка (т) -> 1

ветви (т) -> [дерево (2), дерево (3)]

Любая помощь очень ценится.

Answer 1

Чтобы существовал путь, при каждом рекурсивном вызове головной узел должен быть равен первому элементу в списке путей.Если это не так, то в дереве нет совпадений.Если головной узел действительно равен первому элементу в списке, а длина входного списка равна 1, то полное совпадение обнаружено.При каждом вызове со списком путей длиной > 1 функция должна вызываться в каждой ветви:

def is_path(t, path):
  if t.head != path[0]:
     return False
  if t.head == path[0] and len(path) == 1:
     return True
  return any(is_path(i, path[1:]) for i in t.children)

---

class tree:
  def __init__(self, _head, _children=[]):
    self.head, self.children = _head, _children

t = tree(1, [tree(2, [tree(4), tree(5)]), tree(3, [tree(6), tree(7)])])
print(is_path(t, [1, 2]))
print(is_path(t, [1, 2, 4]))
print(is_path(t, [2, 4]))
print(is_path(t, [1, 3, 7]))

Вывод:

True
True
False
True