Path Sum

+10

Otrzymujesz drzewo binarne zapisane w tablicy tree w kolejności poziomami oraz liczbę targetSum. Korzeń znajduje się pod indeksem 0, dzieci węzła pod indeksem i znajdują się pod indeksami 2*i+1 (lewe) i 2*i+2 (prawe), -1 oznacza puste miejsce, a tablica może kończyć się dodatkowymi wpisami -1. Zwróć true, jeśli istnieje ścieżka od korzenia w dół do liścia, której wartości sumują się do targetSum, a w przeciwnym razie false. Liść to węzeł bez dzieci: oba jego miejsca na dzieci są puste.

Funkcja

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

treeinteger-array: drzewo binarne w porządku poziomami, z wartością -1 oznaczającą puste miejsce
targetSuminteger: łączna wartość, jaką musi osiągnąć ścieżka od korzenia do liścia
Zwracaboolean: true, jeśli suma wartości na którejś ścieżce od korzenia do liścia wynosi targetSum; w przeciwnym razie false

Ograniczenia

1 ≤ tree.length ≤ 32767
Każde tree[i] ma wartość -1 lub wartość, dla której 0 ≤ tree[i] ≤ 1000.
tree[0] nigdy nie jest równe -1, więc drzewo ma co najmniej jeden węzeł.
Tablica może kończyć się dodatkowymi wpisami -1 za ostatnim węzłem.
Oba potomki pustego pola również są puste, a głębokość wynosi najwyżej 14.
0 ≤ targetSum ≤ 15000

Przykłady

Wejście: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 14
Wyjście: true
Wyjaśnienie: Ścieżka 3, 9, 2 (indeksy 0, 1, 4) daje w sumie 14, a 2 na indeksie 4 jest liściem.

Wejście: tree = [3, 9, 6, -1, 2, 1, 7]targetSum = 12
Wyjście: false
Wyjaśnienie: 3 + 9 = 12, ale 9 ma dziecko, więc żadna ścieżka się tam nie kończy. Suma trzech ścieżek od korzenia do liścia wynosi 14, 10 i 16, a żadna z nich nie wynosi 12.

Wejście: tree = [4, -1, -1]targetSum = 4
Wyjście: true
Wyjaśnienie: Oba miejsca na dzieci korzenia są puste, więc korzeń sam w sobie jest liściem. Ścieżka zawierająca tylko 4 daje w sumie 4.

+14 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Czy potrafisz policzyć ścieżki, których suma wynosi targetSum, jeśli ścieżka może zaczynać się w dowolnym węźle i kończyć w dowolnym węźle poniżej niego, a nie tylko biec od korzenia do liścia?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Pytanie dotyczy całych ścieżek, od korzenia aż do liścia. Suma bieżąca może osiągnąć wartość targetSum w połowie ścieżki, w węźle, który nadal ma dzieci — i to się nie liczy. Dlatego przekazujesz sumę ścieżki do tej pory do każdego węzła i porównujesz ją z wartością docelową tylko w liściach. Rekurencja przekazuje tę sumę jako parametr; stos przechowuje ją obok każdego węzła.

Rekurencja dla pozostałej sumy

Intuicja

Najpierw: jak poruszać się po tablicy. Węzeł o indeksie i ma lewe dziecko pod indeksem 2*i+1, a prawe pod indeksem 2*i+2. Dziecko istnieje tylko wtedy, gdy jego indeks mieści się w tablicy, a wartość pod tym indeksem nie wynosi -1. W [3, 9, 6, -1, 2, 1, 7] korzeń 3 ma dzieci pod indeksami 1 i 2, a węzeł 9 pod indeksem 1 ma puste miejsce na lewe dziecko pod indeksem 3 oraz węzeł 2 pod indeksem 4 jako prawe dziecko.

A teraz pomysł. Ścieżka, której suma wynosi targetSum, zaczyna się od wartości korzenia, więc pozostała część ścieżki, która zaczyna się od jednego z dzieci korzenia, musi dawać sumę równą targetSum minus tej wartości. To to samo pytanie dotyczące mniejszego drzewa. Odejmuj wartość każdego węzła podczas schodzenia w dół. Ścieżka kończy się w liściu, więc odpowiedź w tym miejscu zależy od tego, czy nie pozostała już żadna wartość do odjęcia.

W pierwszym przykładzie po korzeniu pozostaje 14 - 3 = 11, po węźle 9 pozostaje 2, a po liściu 2 pozostaje 0: true. W drugim przykładzie po węźle 9 pozostaje już 0, ale ma on dziecko, więc wyszukiwanie trwa dalej, a jego liść kończy z wartością -2. Każdy węzeł jest odwiedzany najwyżej raz, czas O(n), a stos wywołań przechowuje jedną ramkę na poziom, O(h); tutaj najwyżej 15 ramek (głębokość 14 oznacza liczbę krawędzi poniżej korzenia).

Algorytm

Napisz walk(i, remaining) i odejmij tree[i] od remaining.
Jeśli oba miejsca na dzieci i są puste (indeks wykracza poza koniec lub -1), zwróć informację, czy remaining wynosi 0.
W przeciwnym razie zwróć true, jeśli wywołanie walk dla istniejącego lewego dziecka lub istniejącego prawego dziecka zwraca true.
Zwróć walk(0, targetSum).

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)

Przeszukiwanie w głąb z jawnym stosem

Intuicja

Rekurencja przechowuje jedną liczbę dla każdego wywołania: informację, ile jeszcze brakuje do uzyskania wartości docelowej. Możesz samodzielnie przechowywać taką liczbę na stosie obok każdego węzła i pominąć wywołania. Zapisuj sumę ścieżki od korzenia do danego węzła, włącznie z tym węzłem. Zacznij od (0, tree[0]) i każdemu dziecku przypisz sumę wartości rodzica i jego własnej wartości.

Zdejmij parę ze stosu. Jeśli węzeł jest liściem, a jego suma jest równa targetSum, to koniec. W przeciwnym razie dodaj na stos jego istniejące dzieci. W pierwszym przykładzie prawa strona schodzi ze stosu jako pierwsza: liście 7 i 1 mają odpowiednio sumy 16 i 10. Następnie zdejmowana jest para (1, 12) dla węzła 9. To nie jest liść, więc dodaje na stos (4, 14) — liść z właściwą sumą.

Każdy istniejący węzeł jest dodawany na stos raz, więc złożoność czasowa wynosi O(n), a wyszukiwanie kończy się na pierwszym pasującym liściu. Na stosie znajdują się oczekujące węzły rodzeństwa wzdłuż bieżącej ścieżki, mniej więcej jeden na poziom, co oznacza O(h) pamięci. Ta sama pętla działa na głębokim drzewie opartym na wskaźnikach, w którym rekurencja mogłaby wyczerpać stos.

Algorytm

Umieść (0, tree[0]) na stosie.
Zdejmij parę (i, total) ze stosu i sprawdź miejsca na dzieci 2*i+1 oraz 2*i+2.
Jeśli żadne z dzieci nie istnieje i total jest równe targetSum, zwróć true.
Umieść każde istniejące dziecko c jako (c, total + tree[c]) na stosie.
Gdy stos będzie pusty, zwróć false.

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

Pułapki i przypadki brzegowe

Prawie każdy błąd w tym zadaniu dotyczy tego, gdzie kończy się ścieżka.

Porównywanie sumy w każdym węźle. W drugim przykładzie 3 + 9 = 12 zgadza się w węźle 9, który ma dziecko, więc odpowiedzią jest false. Porównuj tylko w liściach.
Traktowanie pustego miejsca na dziecko jako końca ścieżki. Jeśli walk w pustym miejscu zwraca remaining == 0, węzeł 9 w drugim przykładzie zostanie uznany za liść ze względu na puste lewe miejsce. Węzeł jest liściem tylko wtedy, gdy oba miejsca na dzieci są puste.
Zapominanie o samym korzeniu. Pojedynczy węzeł jest liściem, więc [4] z targetSum = 4 daje true, podobnie jak [0] z targetSum = 0.
Przerywanie wyszukiwania, gdy suma przekroczy wartość docelową. Wartości w tym zadaniu nigdy nie są ujemne, więc jest to bezpieczne, ale ten sam kod daje błędne odpowiedzi, gdy tylko drzewo może zawierać wartości ujemne.
Odczyt poza końcem tablicy. Liść blisko końca tablicy może mieć indeksy dzieci wykraczające poza jej ostatni element, ponieważ tablica może kończyć się zaraz po ostatnim węźle. Sprawdź indeks przed odczytaniem tree[c].
Pomylenie przesunięcia w Lua i R, gdzie tablice zaczynają się od 1. Pozostaw indeksy węzłów liczone od 0 na potrzeby obliczeń 2*i+1 i odczytuj tree[i + 1].

Najczęstsze pytania4

Jaka jest złożoność czasowa Path Sum?

Każdy węzeł jest odwiedzany co najwyżej raz, więc złożoność czasowa wynosi O(n), a wyszukiwanie można zakończyć przy pierwszym pasującym liściu. Dodatkowa przestrzeń wynosi O(h) dla eksplorowanej ścieżki, zarówno w postaci ramek wywołań, jak i wpisów na własnym stosie.

Dlaczego Path Sum sprawdza sumę tylko w węzłach liści?

Zadanie wymaga ścieżki od korzenia do liścia, a ścieżka kończąca się w węźle, który ma dzieci, nie jest taką ścieżką. Sprawdzanie każdego węzła zbyt często zwraca true, na przykład gdy sama wartość korzenia jest równa targetSum, ale korzeń ma dziecko. Ścieżka kończy się w węźle tylko wtedy, gdy oba jego miejsca na dzieci są puste.

Czy sumę ścieżki można rozwiązać za pomocą BFS?

Tak. Umieść pary węzła i sumy jego ścieżki w kolejce zamiast na stosie i sprawdzaj każdy liść, gdy z niej wychodzi. Złożoność czasowa nadal wynosi O(n), ale kolejka może pomieścić cały poziom, czyli około połowę węzłów pełnego drzewa, podczas gdy stos przechowuje około jednego węzła na poziom.

Jak znaleźć każdą ścieżkę, której suma daje wartość docelową?

W miarę schodzenia w dół zachowuj listę węzłów na bieżącej ścieżce, kopiuj ją do odpowiedzi przy każdym liściu, którego suma pasuje, i usuwaj ostatni węzeł podczas powrotu w górę. Przechodzenie pozostaje takie samo; zwiększa się tylko ilość zapisywanych informacji. Kopiowanie ścieżek może kosztować więcej niż samo przechodzenie, gdy pasuje wiele liści.

Python

def hasPathSum(tree, targetSum):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

true