Kökten yaprağa hedef toplam
Görev tanımı
Problem
İkili bir ağaç ve bir hedef sayı verildiğinde, kökten bir yaprağa inen bir yolun değerlerinin toplamının tam olarak hedefe eşit olup olmadığına karar ver. Yaprak çocuğu olmayan bir düğümdür; yani bir yol her zaman ağacın dibinde bitmelidir. Değerler negatif olabilir.
Örnekler
Input: tree = 5, left 4 with left child 11 having children 7 and 2,
right 8 with children 13 and 4; target = 22
Output: True
Neden: 5, 4, 11, 2 yolunun toplamı 22
Input: tree = 1 with a single left child 2; target = 1
Output: False
Neden: kök bir yaprak değil, bu yüzden yol orada duramaz
Input: tree = empty; target = 0
Output: False
Neden: edge case: boş bir ağacın hiç kökten yaprağa yolu yok
İpuçları
0 / 3
Ağaç soruyu, her çocuk için bir tane olmak üzere aynı türden iki küçük soruya böler; ikisinden biri evet derse cevap evettir.
Değerleri geri dönerken toplamak yerine aşağı inerken her değeri hedeften çıkar; böylece bir çocuk yalnız hâlâ borçlu olunan miktarı görür.
Kalan miktarı taşıyarak kökten in. Bir yaprakta, kalan tam olarak o yaprağın değerine eşit olduğunda evet cevabını ver. Olmayan bir dalda hayır cevabını ver, böylece tek çocuklu bir düğüm asla bir durma noktası sanılmaz.
- Hedef zaman
- O(n)
- Hedef alan
- O(h)
Kısıtlar
- values may be negative
- a path must end at a leaf
Çözüm
Kalan miktarı aşağı taşımak her düğümdeki soruyu daha küçük bir ağaçta aynı soruya çevirir; böylece tek bir özyineleme (recursion) bütün aramayı kapsar. Olmayan dal durumu kalanı kontrol etmek yerine hayır cevabını vermelidir; aksi halde tek çocuklu bir düğüm geçerli bir bitiş noktası sayılırdı. Bir yaprak kalanı kendi değeriyle karşılaştırarak cevap verir, iki çocuk da kısa devre yapan bir or ile birleştirilir. En kötü durumda zaman O(n), call stack için alan O(h).
class T:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def has_path_sum(node, target):
if node is None:
return False # an absent branch is not a stopping point
rest = target - node.val
if node.left is None and node.right is None:
return rest == 0 # only a leaf may close the path
return has_path_sum(node.left, rest) or has_path_sum(node.right, rest)
print(has_path_sum(T(5, T(4, T(11, T(7), T(2))), T(8, T(13), T(4))), 22)) # -> True
print(has_path_sum(T(1, T(2)), 1)) # -> False
print(has_path_sum(None, 0)) # -> FalseKodda değil de fikirde mi takıldın? Path Sum varyantları bunu anlatıyor.