DSA Interview Prep · leksjon

TreeNode-klassen og BFS nivå for nivå

Konstruer binærtrær fra arrayer, implementer BFS med en deque for utskrift nivå for nivå, og løs maximum-depth med BFS.

Leksjon 1 av 413 trinn

TreeNode-klassen og BFS nivå for nivå er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 1 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.

Grunnlaget for TreeNode-klassen

Et binærtre er en hierarkisk datastruktur der hver node har høyst to barn, kalt venstre og høyre. I Python modellerer vi en node med en enkel klasse: class TreeNode: def __init__(self, val=0, left=None, right=None). Alle treproblemer i intervjuer starter med denne definisjonen – du vil se den i standardkoden til nesten alle LeetCode-oppgaver om trær.

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

# Build a small tree manually:
#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)

Bygge trær fra arrayer

Intervjuproblemer gir deg ofte et tre representert som en array i nivårekkefølge, der None markerer manglende noder. Gitt indeks i finner du venstre barn på 2i+1 og høyre barn på 2i+2. Det er nyttig å skrive en hjelpefunksjon som deserialiserer denne arrayen til lenkede TreeNode-objekter, fordi det sparer tid under øvingsøkter.

from collections import deque

def build_tree(arr):
    if not arr or arr[0] is None:
        return None
    root = TreeNode(arr[0])
    q = deque([root])
    i = 1
    while q and i < len(arr):
        node = q.popleft()
        if i < len(arr) and arr[i] is not None:
            node.left = TreeNode(arr[i])
            q.append(node.left)
        i += 1
        if i < len(arr) and arr[i] is not None:
            node.right = TreeNode(arr[i])
            q.append(node.right)
        i += 1
    return root

root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)

Hva er BFS, og hvorfor en kø?

Bredde-først-søk (BFS) besøker alle noder på dybde d før det besøker noen noder på dybde d+1. Denne traverseringen nivå for nivå er nøyaktig det en kø (FIFO) gir oss: Vi legger roten i køen, behandler deretter én node om gangen og legger hvert barns noder i køen underveis. Pythons collections.deque gir O(1) appendleft og popleft, noe som gjør den til det riktige valget fremfor en vanlig liste.

from collections import deque

def bfs_print(root):
    if not root:
        return
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.val, end=' ')
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root)  # 1 2 3 4

BFS i nivårekkefølge: gruppering etter nivå

Standardvarianten av BFS grupperer noder i nivåer ved å registrere køens størrelse ved starten av hver iterasjon. Behandle nøyaktig så mange noder, samle verdiene deres og gå deretter videre til neste nivå. Dette gir en liste med lister – et svært vanlig format for intervjuproblemer som binærtretraversering i nivårekkefølge, sikksakk-traversering og visning fra høyre side.

from collections import deque

def level_order(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        level_size = len(q)
        level = []
        for _ in range(level_size):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level)
    return result

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root))  # [[1], [2, 3], [4]]

Maksimal dybde med BFS

Maksimal dybde i et binærtre er lik antallet nivåer i BFS-traverseringen. Tell ganske enkelt hvor mange ganger du fullfører en nivåsløyfe. Dette gir en løsning med O(n) tid og O(w) plass, der w er treets maksimale bredde. For et balansert tre er w O(n/2), så plassforbruket i verste fall er O(n).

from collections import deque

def max_depth_bfs(root):
    if not root:
        return 0
    depth = 0
    q = deque([root])
    while q:
        depth += 1
        for _ in range(len(q)):
            node = q.popleft()
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return depth

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

Høyresidevisning av et binærtre

Høyresidevisningen returnerer den siste noden som er synlig når du ser treet fra høyre – altså det siste elementet på hvert nivå i BFS-traverseringen. Dette er en direkte anvendelse av BFS i nivårekkefølge: Samle den siste noden i hver nivåsløyfe. Tidskompleksiteten er O(n), og plasskompleksiteten er O(w) for køen.

from collections import deque

def right_side_view(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        level_size = len(q)
        for i in range(level_size):
            node = q.popleft()
            if i == level_size - 1:
                result.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return result

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root))  # [1, 3, 5]

Sikksakktraversering på nivå

I sikksakktraversering samles oddetallsnivåer fra venstre mot høyre og partallsnivåer fra høyre mot venstre. Den ryddigste implementasjonen lar BFS-køen være uendret og reverserer listene for annethvert nivå før de legges til i resultatet. Spor retningen med et boolsk flagg som snus for hvert nivå. Dette unngår kompleksitet med en dobbeltsidig deque i den indre løkken.

from collections import deque

def zigzag_level_order(root):
    if not root:
        return []
    result = []
    q = deque([root])
    left_to_right = True
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(level if left_to_right else level[::-1])
        left_to_right = not left_to_right
    return result

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))

Analyse av plasskompleksiteten til BFS

BFS bruker O(w)-plass, der w er treets maksimale bredde. For et perfekt binært tre med n noder har det siste nivået (n+1)/2 noder – derfor kan BFS ha opptil n/2 noder i køen samtidig. Dette gjør BFS dårligere når det gjelder plass enn DFS (O(h)) for brede, balanserte trær, men bedre for dypt skjeve trær, der DFS-kallestakkens dybde er lik n.

# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)

# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)

from collections import deque

def skewed_tree(n):
    root = TreeNode(1)
    cur = root
    for i in range(2, n+1):
        cur.right = TreeNode(i)
        cur = cur.right
    return root

root = skewed_tree(10)
print('BFS on skewed tree is safe')

Gjennomsnittet for nivåene i et binært tre

Å beregne gjennomsnittsverdien på hvert nivå er en annen direkte anvendelse av BFS. Summer alle verdiene på et nivå, divider med antallet, og legg resultatet til resultatlisten. Dette problemet tester om De kan utføre aritmetikk i nivåsløyfen. Bruk alltid divisjon med float i Python 3 (operatoren /), og håndter tilfellet med et tomt tre i starten.

from collections import deque

def average_of_levels(root):
    if not root:
        return []
    result = []
    q = deque([root])
    while q:
        size = len(q)
        total = 0
        for _ in range(size):
            node = q.popleft()
            total += node.val
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        result.append(total / size)
    return result

root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root))  # [3.0, 14.5, 11.0]

Minimumsdybde med BFS

Minimumsdybden er avstanden fra roten til den nærmeste bladnoden (en node uten barn). BFS finner denne optimalt: Den første bladnoden som oppdages under nivåvis traversering, befinner seg garantert på minimumsdybden. Returner gjeldende dybde så snart De treffer et blad. Dette er O(n) i verste fall, men avsluttes ofte mye tidligere for balanserte trær.

from collections import deque

def min_depth(root):
    if not root:
        return 0
    q = deque([(root, 1)])
    while q:
        node, depth = q.popleft()
        # A leaf has no children
        if not node.left and not node.right:
            return depth
        if node.left:
            q.append((node.left, depth + 1))
        if node.right:
            q.append((node.right, depth + 1))
    return 0

root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5)  # leaf at depth 2
print(min_depth(root))  # 2

Koble sammen søsken på samme nivå

Problemet med å fylle ut next-right-pekere ber Dem koble hver node til den høyre naboen på samme nivå. Med BFS er dette enkelt: I nivåsløyfen setter De node.next = q[0] for alle noder unntatt den siste. Dette er et klassisk eksempel på at BFS gjør løsningen åpenbar, mens DFS krever nøye sporing av pekere på tvers av undertreene.

from collections import deque

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

def connect(root):
    if not root:
        return root
    q = deque([root])
    while q:
        size = len(q)
        for i in range(size):
            node = q.popleft()
            if i < size - 1:
                node.next = q[0]
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
    return root

print('BFS connect: O(n) time, O(w) space')

Hurtigsjekk

Test forståelsen Deres av konseptene Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen lærte De om: definisjonen av TreeNode-klassen og hvordan trær bygges fra arrays, nivåvis BFS med en deque, der nivåstørrelsen brukes til å gruppere noder, samt anvendelser som maksimaldybde, minimumsdybde, visning fra høyre side, sikksakktraversering og gjennomsnitt per nivå. Deretter utforsker vi rekursive DFS-traverseringsrekkefølger.

Gratis å komme i gang

Lær deg Python med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 30
Leksjoner: 120

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «TreeNode-klassen og BFS nivå for nivå» gratis?

Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «TreeNode-klassen og BFS nivå for nivå», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.

Hva lærer jeg i «TreeNode-klassen og BFS nivå for nivå»?

Konstruer binærtrær fra arrayer, implementer BFS med en deque for utskrift nivå for nivå, og løs maximum-depth med BFS. Du øver på DSA Interview Prep med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med DSA Interview Prep?

Ingen tidligere erfaring er nødvendig. DSA Interview Prep på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.

Hvor lang tid tar leksjonen «TreeNode-klassen og BFS nivå for nivå»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne DSA Interview Prep-leksjonen?

Ja. Alle DSA Interview Prep-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til DSA Interview Prep