Проверка, является ли treeNode предком другого узла

Question

def is_ancestor(node, middle):
    # search down
    if node.data == middle.data:
        return True
    if node.left:
        is_ancestor(node.left, middle)
    if node.right:
        is_ancestor(node.right, middle)
    return False

Я использую эту функцию для рекурсивной проверки, является ли node предком middle.

Допустим, у нас есть дерево, которое выглядит как

    5
   /
  2
   \
    4

и я говорю, что узел - это узел, который указывает на 5, а середина - 2.

При вызове is_ancestor(node_with_5, node_with_2) я ожидаю рекурсивное перемещение node вниз влево и вправои возвращает True всякий раз, когда находит middle.

. Однако моя текущая функция дает мне False, хотя она обнаружит middle в первом рекурсивном вызове.

Любая помощь

Answer 1

Вы должны будете сделать несколько небольших изменений, например:

def is_ancestor(node, middle):
    if node is middle:  # data could coincide, compare nodes directly 
        return True
    if node.left and is_ancestor(node.left, middle):
        return True  # do actually return something
    if node.right and is_ancestor(node.right, middle):
        return True  # do actually return something
    return False

Вы можете получить всю логику еще более кратким способом:

def is_ancestor(node, middle):
    if node is None:
        return False
    if node is middle:
        return True
    return is_ancestor(node.left, middle) or is_ancestor(node.right, middle)