0Pricing
Coding Interview Prep · Lekcja

Średnica, wysokość i drzewa zrównoważone

Obliczą Państwo średnicę i wysokość drzewa podczas jednego przejścia DFS, korzystając z funkcji pomocniczej zwracającej obie wartości, a następnie sprawdzą, czy drzewo jest zrównoważone wysokościowo.

Średnica, wysokość i drzewa zrównoważone to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Wysokość drzewa binarnego

Wysokość (czyli maksymalna głębokość) drzewa binarnego to długość najdłuższej ścieżki od korzenia do dowolnego liścia. Oblicza się ją rekurencyjnie: wysokość dowolnego węzła to 1 + max(height(left), height(right)), a przypadkiem bazowym jest 0 dla węzłów null. To obliczenie post-order ma fundamentalne znaczenie — wysokość jest podstawą obliczania średnicy, sprawdzania równowagi i wykonywania rotacji w drzewach AVL.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def height(root):
    if not root:
        return 0
    return 1 + max(height(root.left), height(root.right))

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
print(height(root))  # 4

Średnica: najdłuższa ścieżka

Średnica drzewa binarnego to długość najdłuższej ścieżki między dowolnymi dwoma węzłami (ścieżka może przechodzić przez korzeń, ale nie musi). Długość ścieżki mierzy się w krawędziach. Dla dowolnego węzła średnica przechodząca przez ten węzeł jest równa height(left) + height(right). Średnica całego drzewa to największa z takich wartości obliczonych dla wszystkich jego węzłów.

def diameter_of_binary_tree(root):
    max_diameter = [0]  # use list to allow closure mutation

    def dfs(node):
        if not node:
            return 0
        left_h = dfs(node.left)
        right_h = dfs(node.right)
        # Diameter through this node
        max_diameter[0] = max(max_diameter[0], left_h + right_h)
        return 1 + max(left_h, right_h)  # height for parent

    dfs(root)
    return max_diameter[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_of_binary_tree(root))  # 3

Jedno przejście DFS do obliczania średnicy

Naiwne podejście wywołuje height() dla każdego węzła, co daje O(n²) dla zrównoważonego drzewa. Optymalne rozwiązanie oblicza wysokość i aktualizuje średnicę podczas jednego przejścia DFS. Kluczowa obserwacja jest taka, że rekurencyjna funkcja dfs() pełni jednocześnie dwie funkcje: zwraca wysokość dla rodzica, a przy okazji aktualizuje globalne maksimum średnicy. Ten post-order o podwójnym zastosowaniu pojawia się w wielu zadaniach dotyczących drzew.

# O(n^2) NAIVE: recomputes height for every node
def diameter_naive(root):
    if not root:
        return 0
    through_root = height(root.left) + height(root.right)
    in_left = diameter_naive(root.left)
    in_right = diameter_naive(root.right)
    return max(through_root, in_left, in_right)

# O(n) OPTIMAL: single DFS pass (shown in previous scene)
# The naive version is O(n^2) because height() is O(n)
# and it is called for every node.
print('Naive: O(n^2) | Optimal single-pass: O(n)')

Sprawdzanie równowagi drzewa binarnego

Drzewo binarne jest zrównoważone względem wysokości, jeśli wysokości lewego i prawego poddrzewa każdego węzła różnią się najwyżej o jeden. Naiwne podejście wywołuje height() dla każdego węzła, co daje O(n²). Optymalne podejście korzysta z tej samej sztuczki jednego przejścia: zwraca -1 jako znacznik wartości oznaczający „niezrównoważone” i propaguje go w górę, przerywając obliczenia natychmiast po znalezieniu niezrównoważonego węzła.

def is_balanced(root):
    def check(node):
        if not node:
            return 0
        left = check(node.left)
        if left == -1:
            return -1  # propagate early exit
        right = check(node.right)
        if right == -1:
            return -1
        if abs(left - right) > 1:
            return -1  # unbalanced here
        return 1 + max(left, right)  # height if balanced

    return check(root) != -1

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5)  # too deep on left
print(is_balanced(root))  # False

Schemat zwracania wartości znacznika

Zwracanie wartości znacznika (-1 dla drzewa niezrównoważonego lub specjalna krotka) jest częstym schematem, gdy pomocnicza funkcja DFS musi przekazać dwa rodzaje informacji: obliczony wynik oraz informację o naruszeniu ograniczenia. Zamiast zgłaszać wyjątki lub używać globalnych flag, należy zakodować błąd w typie zwracanej wartości. Takie podejście jest czytelne, eliminuje stan globalny i naturalnie współpracuje z innymi funkcjami rekurencyjnymi.

# General pattern: return (is_valid, computed_value)
def balanced_height(node):
    if not node:
        return True, 0
    left_ok, left_h = balanced_height(node.left)
    if not left_ok:
        return False, 0  # short-circuit
    right_ok, right_h = balanced_height(node.right)
    if not right_ok:
        return False, 0
    balanced = abs(left_h - right_h) <= 1
    return balanced, 1 + max(left_h, right_h)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ok, h = balanced_height(root)
print(ok, h)  # True 2

Średnica wyrażona w węzłach a w krawędziach

Należy uważnie czytać treść zadania: LeetCode #543 mierzy średnicę w krawędziach, podczas gdy niektóre zadania mierzą ją w węzłach. Jeśli potrzebna jest liczba węzłów, średnica przechodząca przez dany węzeł wynosi height(left) + height(right) + 1 (należy dodać 1 za sam węzeł). Jeśli potrzebna jest liczba krawędzi, trzeba pominąć +1. Przed rozpoczęciem implementacji należy zawsze ustalić tę kwestię z osobą prowadzącą rozmowę rekrutacyjną.

def diameter_in_nodes(root):
    max_path = [0]

    def dfs(node):
        if not node:
            return 0
        left_h = dfs(node.left)
        right_h = dfs(node.right)
        # Path through this node in NODE count
        nodes_through = left_h + right_h + 1
        max_path[0] = max(max_path[0], nodes_through)
        return 1 + max(left_h, right_h)

    dfs(root)
    return max_path[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_in_nodes(root))  # 4 nodes: 4-2-1-3 or 5-2-1-3

Suma ścieżki: dowolna ścieżka od korzenia do liścia

Zadanie sumy ścieżki stawia pytanie: czy istnieje ścieżka od korzenia do liścia, której suma jest równa wartości docelowej? Należy użyć DFS i podczas schodzenia w dół odejmować wartość bieżącego węzła od wartości docelowej. W liściu trzeba sprawdzić, czy pozostała wartość docelowa jest równa wartości tego liścia. Jest to przejście DFS w porządku pre-order, w którym pozostała suma jest przekazywana jako parametr — klasyczny przykład rekurencji odgórnej.

def has_path_sum(root, target):
    if not root:
        return False
    # Leaf node: check if we've exactly hit the target
    if not root.left and not root.right:
        return root.val == target
    remaining = target - root.val
    return (has_path_sum(root.left, remaining) or
            has_path_sum(root.right, remaining))

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22))  # True: 5+4+11+2=22

Maksymalna suma ścieżki (trudniejszy wariant)

Maksymalna suma ścieżki (LeetCode #124) jest znacznie trudniejsza: ścieżka może zaczynać się i kończyć w dowolnym węźle, a wartości mogą być ujemne. Dla każdego węzła należy rozważyć cztery możliwości: sam węzeł, węzeł + gałąź lewa, węzeł + gałąź prawa albo węzeł + obie gałęzie. Tylko trzy pierwsze możliwości mogą zostać przedłużone w kierunku rodzica; czwarta jest kandydatem końcowym do globalnego maksimum.

def max_path_sum(root):
    max_sum = [float('-inf')]

    def gain(node):
        if not node:
            return 0
        # Only take positive contributions
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        # Best path through this node (can't go both ways upward)
        max_sum[0] = max(max_sum[0], node.val + left + right)
        # Return the best single-branch gain for parent
        return node.val + max(left, right)

    gain(root)
    return max_sum[0]

root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_path_sum(root))  # 42: 15+20+7

Drzewa AVL i samobalansowanie

Drzewo AVL to BST, które zachowuje równowagę wysokości dzięki wykonywaniu rotacji po operacjach wstawiania i usuwania. Każdy węzeł przechowuje współczynnik równowagi (wysokość prawego poddrzewa - wysokość lewego poddrzewa), który musi należeć do zbioru {-1, 0, 1}. Gdy wystąpi naruszenie, pojedyncza lub podwójna rotacja przywraca równowagę w czasie O(1), zachowując całkowitą wysokość na poziomie O(log n) i gwarantując złożoność wszystkich operacji O(log n).

# Balance factor = height(right) - height(left)
# AVL invariant: balance factor in {-1, 0, 1} for every node

# Four violation types and their fixes:
# LL (left-heavy left child): single right rotation
# RR (right-heavy right child): single left rotation
# LR (right-heavy left child): left rotate child, then right rotate root
# RL (left-heavy right child): right rotate child, then left rotate root

# Knowing this is enough for interviews; you rarely implement
# full AVL in an interview but must discuss the concept.
print('AVL maintains O(log n) height via rotations')

Sprawdzanie symetrii drzewa

Drzewo binarne jest symetryczne, jeśli stanowi swoje lustrzane odbicie. Należy sprawdzać je rekurencyjnie: drzewo jest symetryczne wtedy i tylko wtedy, gdy dla każdej pary odpowiadających sobie węzłów po obu stronach osi wartości są równe, a ich poddrzewa są swoimi lustrzanymi odbiciami. Należy zdefiniować funkcję pomocniczą is_mirror(left, right), która sprawdza: oba węzły są null (poprawnie), jeden z nich jest null (niepoprawnie), wartości są równe, a poddrzewa wewnętrzne i zewnętrzne są swoimi lustrzanymi odbiciami.

def is_symmetric(root):
    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))

    return is_mirror(root.left, root.right)

sym = TreeNode(1)
sym.left = TreeNode(2)
sym.right = TreeNode(2)
sym.left.left = TreeNode(3)
sym.right.right = TreeNode(3)
print(is_symmetric(sym))  # True

nosym = TreeNode(1)
nosym.left = TreeNode(2)
nosym.right = TreeNode(2)
nosym.left.right = TreeNode(3)
print(is_symmetric(nosym))  # False

Łączenie informacji o wysokości i średnicy drzewa

Wzorzec jednokrotnego przejścia w porządku postorder, w którym funkcja pomocnicza jednocześnie zwraca wysokość i aktualizuje wynik globalny, można ponownie wykorzystać w wielu zadaniach: do wyznaczania średnicy, maksymalnej sumy ścieżki, sprawdzania zrównoważenia, zliczania dobrych węzłów i nie tylko. Zawsze należy zadać sobie pytanie: „jakich informacji potrzebuje rodzic od każdego dziecka?”. To jest wartość zwracana. „Jakie obliczenie jest lokalne dla tego węzła?”. To ono aktualizuje wynik globalny. Taki podział jest kluczową umiejętnością przy rozwiązywaniu trudnych problemów dotyczących drzew.

# Reusable template for post-order dual-purpose DFS:
def tree_problem(root):
    result = [float('-inf')]  # or 0 depending on problem

    def dfs(node):
        if not node:
            return 0  # base return (height, count, etc.)
        left_val = dfs(node.left)
        right_val = dfs(node.right)
        # --- Update global result using both children ---
        candidate = left_val + right_val  # example: diameter
        result[0] = max(result[0], candidate)
        # --- Return info needed by PARENT ---
        return 1 + max(left_val, right_val)  # example: height

    dfs(root)
    return result[0]

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(tree_problem(root))  # diameter = 2

Szybkie sprawdzenie

Proszę sprawdzić, czy rozumieją Państwo zagadnienia z kursu Data Structures & Algorithms — Coding Interview Prep omówione w tej lekcji.

Podsumowanie lekcji

W tej lekcji nauczyli się Państwo: obliczania wysokości za pomocą rekurencyjnego przeszukiwania DFS w porządku postorder, obliczania średnicy w ramach pojedynczego przejścia O(n) z użyciem pomocniczej funkcji DFS o dwóch zastosowaniach oraz sprawdzania zrównoważenia z użyciem wartości sygnalizującej wcześniejsze zakończenie. Następnie zajmiemy się problemami sumy ścieżki i najniższego wspólnego przodka.

Często zadawane pytania

Czy lekcja „Średnica, wysokość i drzewa zrównoważone” jest bezpłatna?

Tak — pełny tekst „Średnica, wysokość i drzewa zrównoważone” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Średnica, wysokość i drzewa zrównoważone”?

Obliczą Państwo średnicę i wysokość drzewa podczas jednego przejścia DFS, korzystając z funkcji pomocniczej zwracającej obie wartości, a następnie sprawdzą, czy drzewo jest zrównoważone wysokościowo. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Średnica, wysokość i drzewa zrównoważone”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Klasa TreeNode i BFS poziomami
  2. DFS w kolejności inorder, preorder i postorder
  3. Średnica, wysokość i drzewa zrównoważone
  4. Suma ścieżki i najniższy wspólny przodek
← Powrót do Coding Interview Prep