Path Sum

Q: Jaka jest złożoność czasowa problemu sumy ścieżki?

O(n) : każdy węzeł jest odwiedzany co najwyżej raz, a wyszukiwanie może zakończyć się przy pierwszym pasującym liściu. Dodatkowa przestrzeń wynosi O(h) dla badanej ścieżki, jako ramki wywołań lub wpisy na własnym stosie.

ŁatwePrzechodzenie drzewa

+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 o indeksie 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 do liścia, której wartości sumują się do targetSum, a w przeciwnym razie false. Liść to węzeł, którego oba miejsca na dzieci są puste.

Funkcja

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

treeinteger-array: drzewo binarne w porządku poziomowym, gdzie -1 oznacza puste miejsce
targetSuminteger: łączna wartość, jaką musi osiągnąć ścieżka od korzenia do liścia
Zwracaboolean: prawda, jeśli suma na którejś ścieżce od korzenia do liścia wynosi <code>targetSum</code>, w przeciwnym razie fałsz

Ograniczenia

1 ≤ tree.length ≤ 32767
Każde tree[i] to -1 albo wartość spełniająca warunek 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 po ostatnim węźle.
Oboje dzieci pustego miejsca również są puste, a głębokość wynosi co 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 pod indeksem 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 wartości na trzech ścieżkach od korzenia do liścia wynosi 14, 10 i 16, a żadna z nich nie daje 12.

Wejście: tree = [4, -1, -1]targetSum = 4
Wyjście: true
Wyjaśnienie: Oba miejsca na dzieci w korzeniu są puste, więc korzeń sam w sobie jest liściem. Suma wartości na ścieżce zawierającej tylko 4 wynosi 4.

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?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Liczą się tylko pełne ścieżki, od korzenia aż do liścia. Suma bieżącej ścieżki może osiągnąć targetSum w węźle, który nadal ma dzieci, a to się nie liczy. Dlatego przekazuj sumę ścieżki do każdego węzła jako parametr albo przechowuj ją na stosie i porównuj z wartością docelową tylko w liściach.

Rekurencja dla pozostałej sumy

Intuicja

Ścieżka, której wartości sumują się do targetSum, zaczyna się od wartości korzenia, więc pozostała jej część, która zaczyna się od jednego z dzieci korzenia, musi sumować się do targetSum pomniejszonego o tę wartość. To to samo pytanie, tylko dotyczące mniejszego drzewa. Odejmuj wartość każdego węzła podczas schodzenia w dół; przy liściu ścieżka się kończy, więc odpowiedzią jest informacja, czy nie pozostało już nic.

W pierwszym przykładzie korzeń pozostawia 14 - 3 = 11, 9 pozostawia 2, a liść 2 pozostawia 0. W drugim 9 pozostawia już 0, ale ma dziecko, więc wyszukiwanie trwa dalej. Każdy węzeł jest odwiedzany raz, czas działania wynosi O(n), a stos wywołań przechowuje jedną ramkę na poziom, maksymalnie 15.

Algorytm

Napisz walk(i, remaining) i odejmij tree[i] od remaining.
Jeśli oba miejsca na dzieci węzła i są puste (indeks wykracza poza koniec lub wynosi -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. Zamiast tego przechowuj ją samodzielnie na stosie obok każdego węzła: sumę ścieżki od korzenia do tego węzła. Zacznij od (0, tree[0]); każde dziecko otrzymuje sumę swojego rodzica powiększoną o własną wartość. Zdejmij parę ze stosu. Jeśli węzeł jest liściem, a suma wynosi targetSum, gotowe; w przeciwnym razie dodaj na stos jego rzeczywiste dzieci.

Każdy rzeczywisty węzeł jest dodawany na stos raz, czas działania wynosi O(n), a stos przechowuje około jednego oczekującego rodzeństwa na poziom, czyli O(h). Ta sama pętla działa na głębokim drzewie opartym na wskaźnikach, w którym podczas rekurencji mogłoby zabraknąć miejsca na stosie.

Algorytm

Umieść (0, tree[0]) na stosie.
Zdejmij parę (i, total) i sprawdź pozycje dzieci 2*i+1 oraz 2*i+2.
Jeśli żadne dziecko nie istnieje, a total jest równe targetSum, zwróć true.
Umieść każde istniejące dziecko c jako (c, total + tree[c]).
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

Porównywanie sumy w każdym węźle. W drugim przykładzie 3 + 9 = 12 pasuje do wartości węzła 9, który ma dziecko, więc odpowiedzią jest false.
Uznawanie pustego miejsca na dziecko za koniec ścieżki. Wtedy w drugim przykładzie 9 kończy ścieżkę przez swoje puste lewe miejsce.
Pomijanie samego korzenia. Pojedynczy węzeł jest liściem, więc dla [4] z celem 4 wynikiem jest true, podobnie jak dla [0] z celem 0.
Odczytywanie elementów poza końcem tablicy. Liść blisko końca może mieć indeksy dzieci przekraczające indeks ostatniego elementu.
Mylenie przesunięcia w Lua i R. Zachowaj indeksy węzłów liczone od 0 dla 2*i+1 i odczytuj tree[i + 1].

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu sumy ścieżki?

O(n): każdy węzeł jest odwiedzany co najwyżej raz, a wyszukiwanie może zakończyć się przy pierwszym pasującym liściu. Dodatkowa przestrzeń wynosi O(h) dla badanej ścieżki, jako ramki wywołań lub wpisy na własnym stosie.

Czy Path Sum można rozwiązać za pomocą BFS?

Tak. Umieść pary składające się z węzła i sumy ścieżki w kolejce zamiast na stosie i sprawdzaj każdy liść, gdy z niej wyjmuje się elementy. Złożoność czasowa nadal wynosi O(n), ale kolejka może przechowywać cały poziom, czyli około połowy 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 jest równa wartości docelowej?

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

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

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik

true