Path Sum

+10

Sana, seviye sırasına göre dizide saklanan bir ikili ağaç tree ve bir sayı targetSum veriliyor. Kök 0 indeksinde bulunur, i indeksindeki düğümün çocukları 2*i+1 (sol) ve 2*i+2 (sağ) indekslerinde bulunur, -1 boş bir yeri belirtir ve dizinin sonunda fazladan -1 girdileri olabilir. Kökten bir yaprağa kadar olan herhangi bir yolun değerleri toplamı targetSum ediyorsa true, aksi hâlde false döndür. Yaprak, çocuğu olmayan düğümdür: her iki çocuk yeri de boştur.

Fonksiyon

hasPathSum(tree: integer-array, targetSum: integer) → boolean

treeinteger-array: ikili ağacı seviye sırasına göre, boş konumlar için -1 kullanarak
targetSuminteger: kökten yaprağa giden bir yolun ulaşması gereken toplam
Döndürürboolean: kökten yaprağa giden yollardan herhangi birinin toplamı targetSum değerine eşitse true, aksi takdirde false

Kısıtlar

1 ≤ tree.length ≤ 32767
Her tree[i] değeri -1 veya 0 ≤ tree[i] ≤ 1000 koşulunu sağlayan bir değerdir.
tree[0] hiçbir zaman -1 değildir, bu nedenle ağacın en az bir düğümü vardır.
Dizi, son düğümden sonra fazladan -1 girdileriyle bitebilir.
Boş bir noktanın her iki çocuğu da boştur ve derinlik en fazla 14'tür.
0 ≤ targetSum ≤ 15000

Örnekler

Girdi: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
Çıktı: true
Açıklama: 3, 9, 2 yolu (indeksler 0, 1, 4) toplamda 14 eder ve 4 indeksindeki 2 bir yaprak düğümdür.

Girdi: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
Çıktı: false
Açıklama: 3 + 9 = 12, ancak 9'un bir çocuğu var, bu yüzden hiçbir yol orada bitmez. Kökten yaprağa giden üç yolun toplamı 14, 10 ve 16'dır ve bunların hiçbiri 12 değildir.

Girdi: tree = [4, -1, -1]targetSum = 4
Çıktı: true
Açıklama: Kökün her iki çocuk konumu da boş olduğundan, kök tek başına bir yapraktır. Yalnızca 4 içeren yolun toplamı 4 eder.

Gönderirken +14 gizli test

Ek soru

Bir yolun herhangi bir düğümde başlayıp onun altındaki herhangi bir düğümde bitebildiği, yani yalnızca kökten bir yaprak düğüme gitmesinin gerekmediği durumda, toplamı targetSum olan yolları sayabilir misin?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Soru, kökten bir yaprağa kadar uzanan yolların tamamıyla ilgilidir. Devam eden toplam, yolun ortasında, hâlâ çocukları olan bir düğümde targetSum değerine ulaşabilir; bu sayılmaz. Bu yüzden o ana kadarki yolun toplamını her düğüme taşırsın ve hedefle yalnızca yapraklarda karşılaştırırsın. Özyineleme bu toplamı parametre olarak taşır; yığın ise her düğümün yanında taşır.

Kalan toplam üzerinde özyineleme

Sezgi

Önce, dizi içinde nasıl ilerleyeceğimize bakalım. i indeksindeki düğümün sol çocuğu 2*i+1, sağ çocuğu ise 2*i+2 indeksindedir. Bir çocuk, yalnızca indeksi dizinin içindeyse ve oradaki değer -1 değilse gerçektir. [3, 9, 6, -1, 2, 1, 7] dizisinde kök 3’ün çocukları 1 ve 2 indekslerindedir; 1 indeksindeki 9’un ise 3 indeksinde boş bir sol konumu ve sağında 4 indeksinde 2 vardır.

Şimdi fikre bakalım. Toplamı targetSum olan bir yol kökün değeriyle başlar; bu nedenle yolun geri kalan kısmının, yani kökün çocuklarından birinden başlayan kısmın toplamı targetSum eksi kökün değeri olmalıdır. Bu, daha küçük bir ağaç üzerinde sorulan aynı sorudur. Aşağı inerken her düğümün değerini çıkarın. Bir yaprakta yol sona erer; dolayısıyla oradaki yanıt, geriye hiçbir şey kalıp kalmadığıdır.

İlk örnekte kökten geriye 14 - 3 = 11, 9’dan geriye 2 ve yaprak 2’den geriye 0 kalır: true. İkinci örnekte 9’dan geriye zaten 0 kalır, ancak bir çocuğu olduğundan arama devam eder ve yaprağında sonuç -2 olur. Her düğüm en fazla bir kez ziyaret edilir; zaman karmaşıklığı O(n)’dir. Çağrı yığını her seviye için bir çerçeve tutar; karmaşıklığı O(h)’dir ve burada en fazla 15 çerçeve bulunur (14 derinlik, kökün altındaki kenarların sayısını ifade eder).

Algoritma

walk(i, remaining) yazın ve tree[i] değerini remaining değerinden çıkarın.
i indeksindeki her iki çocuk konumu da boşsa (indeks sonu geçmişse veya -1 ise), remaining değerinin 0 olup olmadığını döndürün.
Aksi hâlde, gerçek bir sol çocuk veya gerçek bir sağ çocuk üzerinde walk çağrısı true döndürüyorsa true döndürün.
walk(0, targetSum) değerini döndürün.

def hasPathSum(tree, targetSum):
    n = len(tree)

    def walk(i, remaining):
        # remaining is what the path still needs once it reaches node i.
        remaining -= tree[i]
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right:
            return remaining == 0  # a leaf: the path ends here
        return (has_left and walk(left, remaining)) or (has_right and walk(right, remaining))

    return walk(0, targetSum)

Yığıt kullanarak derinlik öncelikli arama

Sezgi

Özyineleme, her çağrıda bir sayı tutar: hedeften ne kadar kaldığı. Böyle bir sayıyı kendin de tutabilir, her düğümün yanındaki bir yığına koyabilir ve çağrıları ortadan kaldırabilirsin. Kökten düğüme kadar olan yolun toplamını, düğümün kendisi de dahil olacak şekilde sakla. (0, tree[0]) ile başla ve her çocuğa ebeveyninin toplamı ile kendi değerinin toplamını ver.

Bir ikili çıkar. Düğüm yapraksa ve toplamı targetSum değerine eşitse, işin tamamdır. Aksi hâlde gerçek çocuklarını yığına ekle. İlk örnekte sağ taraf yığından önce çıkar: 7 ve 1 yapraklarının toplamları 16 ve 10 olur. Ardından 9 için (1, 12) çıkarılır. Bu bir yaprak değildir, bu yüzden doğru toplama sahip bir yaprak olan (4, 14) yığına eklenir.

Her gerçek düğüm yığına bir kez eklenir; dolayısıyla zaman karmaşıklığı O(n) olur ve arama, eşleşen ilk yaprakta durur. Yığın, geçerli yol boyunca bekleyen kardeş düğümleri tutar; her düzey için yaklaşık bir tane, yani O(h) alan. Aynı döngü, özyinelemenin yığın belleğini tüketebileceği derin, işaretçi tabanlı bir ağaçta da çalışır.

Algoritma

(0, tree[0]) çiftini bir yığına ekle.
(i, total) çiftini yığından çıkar ve 2*i+1 ile 2*i+2 çocuk konumlarına bak.
İki çocuk da gerçek değilse ve total, targetSum'a eşitse true döndür.
Her gerçek c çocuğunu (c, total + tree[c]) olarak yığına ekle.
Yığın boşaldığında false döndür.

def hasPathSum(tree, targetSum):
    n = len(tree)
    stack = [(0, tree[0])]  # (node index, sum of the path from the root to it)
    while stack:
        i, total = stack.pop()
        left, right = 2 * i + 1, 2 * i + 2
        has_left = left < n and tree[left] != -1
        has_right = right < n and tree[right] != -1
        if not has_left and not has_right and total == targetSum:
            return True  # a leaf whose path adds up
        if has_left:
            stack.append((left, total + tree[left]))
        if has_right:
            stack.append((right, total + tree[right]))
    return False

Tuzaklar ve uç durumlar

Bu problemdeki neredeyse tüm hatalar, bir yolun nerede bittiğiyle ilgilidir.

Her düğümdeki toplamı karşılaştırmak. İkinci örnekte 3 + 9 = 12, bir çocuğu olan 9 düğümünde eşleşir; bu nedenle yanıt false olur. Yalnızca yapraklarda karşılaştırma yapın.
Boş bir çocuk konumunu yolun sonu olarak değerlendirmek. Boş bir konumda walk, remaining == 0 döndürürse ikinci örnekteki 9, boş sol konumu üzerinden bir yaprak sayılır. Bir düğüm, yalnızca her iki çocuk konumu da boş olduğunda yapraktır.
Tek başına kökü unutmak. Tek bir düğüm bir yapraktır; bu nedenle targetSum = 4 için [4] true olur; targetSum = 0 için [0] da öyle.
Toplam hedefi geçince aramayı kesmek. Buradaki değerler hiçbir zaman negatif olmadığı için bu problemde güvenlidir; ancak bir ağaç negatif değerler içerebildiği anda aynı kod yanlış yanıtlar verir.
Dizinin sonunu aşarak okumak. Dizi son düğümden hemen sonra bitebileceği için sona yakın bir yaprağın çocuk indeksleri son girdisinin ötesinde olabilir. tree[c] okumadan önce indeksi kontrol edin.
Dizilerin 1'den başladığı Lua ve R'deki ötelemeyi karıştırmak. 2*i+1 aritmetiği için düğüm indekslerini 0 tabanlı tutun ve tree[i + 1] okuyun.

Sıkça sorulan sorular4

Path Sum'in zaman karmaşıklığı nedir?

Her düğüm en fazla bir kez ziyaret edilir; bu nedenle zaman karmaşıklığı O(n) olur ve arama eşleşen ilk yaprakta durabilir. Ek alan, ister çağrı çerçeveleri ister kendi yığınınızdaki girdiler olarak olsun, incelenen yol için O(h) olur.

Path Sum neden toplamı yalnızca yaprak düğümlerde kontrol ediyor?

Problem, kökten yaprağa giden bir yol istiyor ve çocukları olan bir düğümde duran yol, böyle bir yol değildir. Her düğümde kontrol etmek, örneğin yalnızca kökün değeri hedefe eşit olduğunda ama kökün bir çocuğu bulunduğunda, çok sık true döndürür. Bir düğüm, yalnızca iki çocuk konumu da boş olduğunda bir yolu sonlandırır.

Yol Toplamı BFS ile çözülebilir mi?

Evet. Yığıt yerine kuyruğa bir düğüm ve yol toplamından oluşan çiftleri koyun ve çıkan her yaprak düğümü kontrol edin. Zaman karmaşıklığı hâlâ O(n) olur, ancak kuyruk, tam bir ağacın düğümlerinin yaklaşık yarısı olan bir seviyenin tamamını tutabilirken yığıt seviye başına yaklaşık bir düğüm tutar.

Toplamı hedef değere eşit olan tüm yolları nasıl bulursun?

Aşağı inerken mevcut yoldaki düğümlerin listesini tutun, toplamı eşleşen her yaprakta bunu yanıta kopyalayın ve yukarı çıkarken son düğümü kaldırın. Dolaşım aynı kalır; yalnızca izlenen bilgiler artar. Çok sayıda yaprak eşleştiğinde yolları kopyalamak, dolaşımın kendisinden daha maliyetli olabilir.

Python

def hasPathSum(tree, targetSum):
    # Kodu buraya yazın

Test durumları

Durum 1

Durum 2

Durum 3

Girdi

tree = [3, 9, 6, -1, 2, 1, 7]
targetSum = 14

Beklenen

true