TreeNode-klassen och BFS nivå för nivå
Skapa binära träd från arrayer, implementera BFS med en deque för utskrift nivå för nivå och lös maximum-depth med BFS.
TreeNode-klassen och BFS nivå för nivå är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 1 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Grunden för TreeNode-klassen
Ett binärt träd är en hierarkisk datastruktur där varje nod har högst två barn, som kallas vänster och höger. I Python modellerar vi en nod med en enkel klass: class TreeNode: def __init__(self, val=0, left=None, right=None). Alla trädproblem i intervjuer börjar med denna definition – ni kommer att se den i standardkoden för nästan alla trädproblem på LeetCode.
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)Bygga träd från arrayer
Intervjuproblem ger ofta ett träd som en array i nivåordning, där None markerar saknade noder. Givet index i finns det vänstra barnet på 2i+1 och det högra på 2i+2. Att skriva en hjälpfunktion som deserialiserar arrayen till länkade TreeNode-objekt är ett värdefullt verktyg som sparar tid under övningssessioner.
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)Vad är BFS och varför en kö?
Bredden-först-sökning (BFS) besöker alla noder på djup d innan den besöker någon nod på djup d+1. Denna traversering nivå för nivå är exakt vad en kö (FIFO) ger oss: vi lägger roten i kön och bearbetar sedan noderna en i taget, samtidigt som vi lägger varje nods barn i kön. Pythons collections.deque ger O(1) för appendleft och popleft, vilket gör den till rätt val framför en vanlig lista.
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 4BFS i nivåordning: gruppering per nivå
Den vanliga BFS-varianten grupperar noder i nivåer genom att registrera köstorleken i början av varje iteration. Bearbeta exakt så många noder, samla deras värden och gå sedan vidare till nästa nivå. Resultatet blir en lista med listor – ett mycket vanligt utdataformat i intervjuer för problem som nivåordningstraversering av binärt träd, sicksacktraversering och höger sidovy.
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]]Maximalt djup med BFS
Ett binärt träds maximala djup är lika med antalet nivåer i dess BFS-traversering. Räkna helt enkelt hur många gånger ni slutför en nivåloop. Då får ni en lösning med O(n) tid och O(w) utrymme, där w är trädets maximala bredd. För ett balanserat träd är w O(n/2), så utrymmet i värsta fall är 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)) # 3Höger sidovy av ett binärt träd
Den högra sidovyn returnerar den sista nod som syns när man betraktar trädet från höger – det vill säga det sista elementet på varje nivå i BFS-traverseringen. Detta är en direkt tillämpning av BFS i nivåordning: samla den sista noden i varje nivåloop. Tidskomplexiteten är O(n) och utrymmet är O(w) för kön.
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]Zigzag-traversering på nivåerna
I en zigzag-traversering samlas udda nivåer från vänster till höger och jämna nivåer från höger till vänster. Den renaste implementationen låter BFS-kön vara oförändrad och vänder helt enkelt på listorna för varannan nivå innan de läggs till i resultatet. Håll reda på riktningen med en boolesk flagga som växlar för varje nivå. Detta undviker komplexiteten hos en dubbelsidig deque i den inre loopen.
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))Analys av BFS:s minneskomplexitet
BFS använder O(w) minne, där w är trädets maximala bredd. För ett perfekt binärt träd med n noder har den sista nivån (n+1)/2 noder — BFS kan alltså hålla upp till n/2 noder i kön samtidigt. Detta gör BFS sämre minnesmässigt än DFS (O(h)) för breda, balanserade träd, men bättre för djupt snedfördelade träd där DFS-anropsstackens djup är 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')Medelvärde för nivåerna i ett binärt träd
Att beräkna medelvärdet på varje nivå är ännu en direkt tillämpning av BFS. Summera alla värden på en nivå, dividera med antalet och lägg till resultatet i resultatlistan. Problemet testar att ni kan utföra aritmetik i nivåloopen. Använd alltid float-division i Python 3 (operatorn /) och hantera fallet med ett tomt träd i början.
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]Minsta djup med BFS
Det minsta djupet är avståndet från roten till den närmaste lövnoden (en nod utan barn). BFS hittar detta optimalt: den första lövnoden som påträffas under nivåordningen ligger garanterat på det minsta djupet. Returnera det aktuella djupet så snart ni når ett löv. Detta är O(n) i värsta fall, men avslutas ofta mycket tidigare för balanserade träd.
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)) # 2Koppla ihop noder på samma nivå
Problemet med att fylla i next-right-pekare går ut på att koppla varje nod till sin högra granne på samma nivå. Med BFS är detta enkelt: ange node.next = q[0] i nivåloopen för alla noder utom den sista. Detta är ett klassiskt exempel där BFS gör lösningen uppenbar, medan DFS kräver noggrann pekarhantering mellan delträd.
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')Snabbkontroll
Testa er förståelse av begreppen Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionssammanfattning
I den här lektionen har ni lärt er: definitionen av klassen TreeNode och hur man bygger träd från arrayer, nivåordnad BFS med en deque där nivåstorleken används för att gruppera noder, samt tillämpningar som maximalt djup, minsta djup, vy från höger sida, zigzag-traversering och medelvärden per nivå. Härnäst utforskar vi rekursiva DFS-traverseringsordningar.
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”TreeNode-klassen och BFS nivå för nivå” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”TreeNode-klassen och BFS nivå för nivå”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”TreeNode-klassen och BFS nivå för nivå”?
Skapa binära träd från arrayer, implementera BFS med en deque för utskrift nivå för nivå och lös maximum-depth med BFS. Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”TreeNode-klassen och BFS nivå för nivå”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- TreeNode-klassen och BFS nivå för nivå
- In-order, pre-order och post-order DFS
- Diameter, höjd och balanserade träd
- Summor av vägar och närmaste gemensamma förfader