Рекурсия в двоичных деревьях для возврата значения bool?

Question

Я хочу создать рекурсивную функцию, которая принимает двоичное дерево в качестве параметра и возвращает True, если каждый лист под узлом больше, чем его родитель.Если только один узел не удовлетворяет этому условию, вся функция должна возвращать False.

Однако я изо всех сил пытаюсь придумать базовый случай, а также полностью понять, как остановить функцию и вернуть False, если хотя бы одна часть дерева не удовлетворяет условию.Любая помощь будет принята с благодарностью.

Answer 1

Используя рекурсию, что-то вроде этого должно работать:

def children_gt_parent(node, parent_val):
    if node is None:
        return True
    if node.value <= parent_val:
        return False
    return children_gt_parent(node.left, node.value) and children_gt_parent(node.right, node.value)

Затем вы называете это как:

tf = children_gt_parent(root, root.value)

Answer 2

При повторении по дереву базовым случаем будет конечный узел, то есть узел без дочерних элементов.Для такого узла вы могли бы предположить, что он прошел тест (поскольку в противном случае ваш алгоритм должен был бы уже вернуть false), поэтому вы должны вернуть true.

В общем случае вы захотите проверить,узел меньше, чем оба его потомка, и если нет, возвращает False.В противном случае, чтобы убедиться, что условие выполняется для обоих детей, вы должны вернуть результат повторения по левой стороне and результат повторения по правой стороне:

return check(node.left) and check(node.right)