Path Sum

Q: Path Sum'ın zaman karmaşıklığı nedir?

O(n) : Her düğüm en fazla bir kez ziyaret edilir ve arama, eşleşen ilk yaprakta durabilir. Ek alan, çağrı yığınındaki çerçeveler veya kendi yığınınızdaki girdiler olarak, incelenen yol için O(h) olur.

KolayAğaç dolaşma

+10

Seviye sırasına göre tree dizisinde saklanan bir ikili ağaç ve targetSum sayısı 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 konumu belirtir ve dizinin sonunda fazladan -1 girdileri bulunabilir. Kökten bir yaprağa giden herhangi bir yolun değerleri toplamı targetSum ise true, değilse false döndür. Yaprak, her iki çocuk konumu da boş olan bir düğümdür.

Fonksiyon

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

treeinteger-array: ikili ağacı seviye sırasına göre, boş bir yer 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 ise true, aksi takdirde false

Kısıtlar

1 ≤ tree.length ≤ 32767
Her tree[i], -1 ya da 0 ≤ tree[i] ≤ 1000 koşulunu sağlayan bir değerdir.
tree[0] hiçbir zaman -1 değildir, dolayısıyla ağaçta 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 olur.
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 nedenle hiçbir yol orada bitmiyor. Kökten yaprağa giden üç yolun toplamı 14, 10 ve 16 ediyor ve bunların hiçbiri 12 değil.

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

Ek soru

Bir yol herhangi bir düğümde başlayıp onun altındaki herhangi bir düğümde bitebiliyorsa, 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

Yalnızca kökten bir yaprağa kadar olan tam yollar sayılır. Devam eden toplam, hâlâ çocukları olan bir düğümde targetSum değerine ulaşabilir; ancak bu sayılmaz. Bu nedenle yolun toplamını bir parametre olarak veya yığında her düğüme kadar taşı ve hedefle yalnızca yapraklarda karşılaştır.

Kalan toplam üzerinden özyineleme

Sezgi

Toplamı targetSum olan bir yol kökün değeriyle başlar; dolayısıyla kökün çocuklarından birinde başlayan yolun geri kalanının toplamı targetSum değerinden bu değer çıkarıldığında kalan olmalıdır. Bu, daha küçük bir ağaçta sorulan aynı sorudur. Aşağı doğru inerken her düğümün değerini çıkarın; yaprakta yol sona erer, dolayısıyla geriye hiçbir şey kalıp kalmadığı yanıtı verir.

İlk örnekte kökten geriye 14 - 3 = 11, 9 düğümünden geriye 2 ve yaprak 2 düğümünden geriye 0 kalır. İkinci örnekte 9 düğümünden geriye zaten 0 kalır, ancak bir çocuğu vardır; bu yüzden arama devam eder. Her düğüm bir kez ziyaret edilir; zaman karmaşıklığı O(n) olur ve çağrı yığını her seviye için bir çerçeve tutar, en fazla 15.

Algoritma

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

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)

Açık bir yığınla derinlik öncelikli arama

Sezgi

Özyineleme her çağrıda bir sayı tutar. Bunun yerine, her düğümün yanındaki bir yığında kendin tut: kökten o düğüme kadar olan yolun toplamını. (0, tree[0]) ile başla; her çocuğun toplamı, ebeveyninin toplamı ile kendi değerinin toplamıdır. Bir çift çıkar. Düğüm toplamı targetSum olan bir yapraksa işin bitmiştir; değilse gerçek çocuklarını yığına ekle.

Her gerçek düğüm bir kez yığına eklenir; zaman karmaşıklığı O(n) olur ve yığın, her seviyede bekleyen yaklaşık bir kardeş düğüm tutar; O(h). Aynı döngü, özyinelemenin yığın belleğini tüketebileceği derin, işaretçi tabanlı bir ağaçta da çalışır.

Algoritma

Yığına (0, tree[0]) ekle.
Bir (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 değerine 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

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 yüzden yanıt false olur.
Boş bir çocuk konumunun bir yolu bitirmesine izin vermek. Böylece ikinci örnekteki 9, boş sol konumu üzerinden bir yolu bitirir.
Tek başına kökü gözden kaçırmak. Tek bir düğüm yaprak düğümdür; bu nedenle hedefi 4 olan [4] için yanıt true, hedefi 0 olan [0] için de yanıt true olur.
Dizinin sonundan sonrasını okumak. Sona yakın bir yaprak düğümün çocuk indeksleri son girdiyi aşabilir.
Lua ve R'deki ofseti karıştırmak. Düğüm indekslerini 2*i+1 için 0 tabanlı tutun ve tree[i + 1] okuyun.

Sıkça sorulan sorular3

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

O(n): Her düğüm en fazla bir kez ziyaret edilir ve arama, eşleşen ilk yaprakta durabilir. Ek alan, çağrı yığınındaki çerçeveler veya kendi yığınınızdaki girdiler olarak, incelenen yol için O(h) olur.

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

Evet. Bir düğüm ve o düğümün yol toplamından oluşan çiftleri yığın yerine kuyruğa koy ve sıradan çıktıkça her yaprağı kontrol et. Zaman karmaşıklığı yine O(n) olur, ancak kuyruk bir seviyenin tamamını, yani tam bir ağacın düğümlerinin yaklaşık yarısını tutabilirken yığın her seviye için yaklaşık bir düğüm tutar.

Hedefe ulaşan tüm yolları nasıl bulursun?

Aşağı inerken geçerli yoldaki düğümlerin listesini tutun, toplamı eşleşen her yaprakta bunu yanıta kopyalayın ve yukarı dönerken son düğümü kaldırın. Gezinme aynı kalır. Çok sayıda yaprak eşleştiğinde yolları kopyalamak, gezinmeden daha maliyetli olabilir.

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

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı

true