Bilgiyi aşağı taşımak

Bazı sorularda bir düğüm yalnızca çocuklarına bakarak karar veremez; yukarıdan gelen bilgiye ihtiyacı vardır. Kökten yaprağa giden bir yolun toplamı hedefe eşit mi? Her düğüme "buraya kadar ne kaldı" bilgisini parametre olarak verirsin; yaprağa vardığında kalan tam olarak yaprağın değeriyse yol bulunmuştur.

1def has_path(node, left):
2    if node is None:
3        return False
4    if node.left is None and node.right is None:
5        return left == node.val
6    rest = left - node.val
7    return has_path(node.left, rest) or has_path(node.right, rest)

Arama ağacı kontrolü aynı fikirle çalışır: her düğüme, değerinin içinde kalması gereken aralığı verirsin. Sola inerken üst sınır düğümün değeri olur, sağa inerken alt sınır. Böylece bir düğüm yalnızca babasıyla değil, yukarıdaki bütün atalarıyla karşılaştırılmış olur.