Diameter, højde og balancerede træer
Beregn et træs diameter og højde i én DFS-gennemgang med en hjælper, der returnerer begge værdier, og kontrollér derefter, om træet er højdebalanceret.
Diameter, højde og balancerede træer er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Et binært træs højde
Et binært træs højde (eller maksimale dybde) er længden af den længste vej fra roden til en bladknude. Den beregnes rekursivt: Højden for enhver knude er 1 + max(height(left), height(right)), med et basistilfælde på 0 for null-knuder. Denne postordensberegning er grundlæggende — højden danner grundlag for diameter, balancetjek og rotationer i AVL-træer.
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)) # 4Diameter: Den længste vej
Et binært træs diameter er den længste vej mellem to vilkårlige knuder (vejen går måske gennem roden, men behøver ikke gøre det). Veјlængden måles i kanter. For enhver knude er diameteren gennem den lig med height(left) + height(right). Den samlede diameter er den største af disse værdier blandt alle knuder i træet.
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Ét DFS-gennemløb til diameteren
Den naive metode kalder height() ved hver knude — O(n²) for et balanceret træ. Den optimale løsning beregner højden og opdaterer diameteren i ét DFS-gennemløb. Den centrale indsigt er, at den rekursive funktion dfs() tjener to formål samtidigt: Den returnerer højden til forælderen, mens den opdaterer en global maksimal diameter som bivirkning. Dette dobbeltformål med postordenslogik optræder i mange træopgaver.
# 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)')Tjek af balanceret binært træ
Et binært træ er højdebalanceret, hvis højderne af hvert nodes venstre og højre undertræ højst adskiller sig med én. Den brute force-baserede metode kalder height() ved hver knude — O(n²). Den optimale metode bruger det samme trick med ét gennemløb: Returnér -1 som signalværdi for 'ubalanceret', og før den op gennem træet, så gennemløbet afsluttes tidligt, så snart en ubalanceret knude findes.
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)) # FalseMønstret med en signalværdi som returværdi
Returnering af en signalværdi (-1 for ubalanceret eller en særlig tuple) er et almindeligt mønster, når en DFS-hjælpefunktion skal signalere to slags oplysninger: det beregnede resultat og om en begrænsning blev overtrådt. I stedet for at udløse undtagelser eller bruge globale flag koder du fejlen i returtypen. Denne metode er enkel, undgår global tilstand og fungerer naturligt sammen med andre rekursive hjælpefunktioner.
# 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 2Diameter målt i knuder eller kanter
Vær opmærksom på problemformuleringen: LeetCode #543 måler diameter i kanter, mens nogle opgaver måler den i knuder. Hvis du skal tælle knuder, er diameteren gennem en knude height(left) + height(right) + 1 (læg 1 til for selve knuden). Hvis du skal tælle kanter, skal du udelade +1. Afklar altid dette med intervieweren, før du begynder at programmere.
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-3Summen af enhver vej fra rod til blad
Problemet med vejens sum spørger: Er summen af en vej fra rod til blad lig med en målværdi? Brug DFS, og træk den aktuelle knudes værdi fra målet, mens du bevæger dig ned gennem træet. Ved en bladknude skal du kontrollere, om den resterende målværdi er lig med bladknudens værdi. Dette er et præordens-DFS, hvor du sender den resterende sum med som parameter — et klassisk eksempel på top-til-bund-rekursion.
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=22Maksimal vej-sum (vanskelig variant)
Den maksimale vej-sum (LeetCode #124) er betydeligt vanskeligere: Vejen kan begynde og slutte ved en vilkårlig knude, ikke kun fra rod til blad, og værdierne kan være negative. Ved hver knude skal du overveje fire muligheder: kun selve knuden, knuden + venstre gren, knuden + højre gren eller knuden + begge grene. Kun de tre første kan fortsætte op til forælderen; den fjerde er en afsluttende kandidat til den globale maksimumværdi.
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+7AVL-træer og selvbalancering
Et AVL-træ er et BST, der opretholder højdebalancen ved at udføre rotationer efter indsættelses- og sletteoperationer. Hver knude gemmer en balancefaktor (højde(højre) - højde(venstre)), som skal forblive i {-1, 0, 1}. Når der opstår en overtrædelse, genskaber en enkelt eller dobbelt rotation balancen på O(1)-tid, så den samlede højde forbliver O(log n), og alle operationer garanteret er 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')Tjek af symmetrisk træ
Et binært træ er symmetrisk, hvis det er et spejlbillede af sig selv. Kontrollér det rekursivt: Træet er symmetrisk, hvis hvert par af tilsvarende knuder på hver sin side af aksen har samme værdier, og deres undertræer er spejlbilleder af hinanden. Definér en hjælpefunktion is_mirror(left, right), der kontrollerer: begge er null (ok), den ene er null (ikke ok), værdierne er ens, og de indre og ydre undertræer er spejlbilleder.
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)) # FalseSammenkobling af højde og diameter
Mønsteret med post-order i ét gennemløb, hvor en hjælpefunktion samtidig returnerer højden og opdaterer et globalt resultat, kan genbruges i mange problemer: diameter, maksimal stisum, kontrol af balance, optælling af gode noder og meget mere. Spørg altid: 'Hvilke oplysninger har forælderen brug for fra hvert barn?' Det er returværdien. 'Hvilken beregning hører lokalt til denne node?' Den beregning opdaterer det globale svar. Denne opdeling er den vigtigste færdighed i svære problemer med træer.
# 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 = 2Hurtigt tjek
Afprøv din forståelse af begreberne fra lektionen i Data Structures & Algorithms — Coding Interview Prep.
Opsummering af lektionen
I denne lektion lærte du: beregning af højde ved hjælp af rekursiv DFS i post-order, beregning af diameter i ét O(n)-gennemløb ved hjælp af en DFS-hjælpefunktion med to formål og kontrol af balance med en stopmarkør til tidligt stop. Nu går vi videre til problemer med stisummer og laveste fælles forfader.
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Diameter, højde og balancerede træer” gratis?
Ja — hele teksten til “Diameter, højde og balancerede træer” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Diameter, højde og balancerede træer”?
Beregn et træs diameter og højde i én DFS-gennemgang med en hjælper, der returnerer begge værdier, og kontrollér derefter, om træet er højdebalanceret. Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Diameter, højde og balancerede træer”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- TreeNode-klassen og BFS niveau for niveau
- In-order, pre-order og post-order DFS
- Diameter, højde og balancerede træer
- Path sum og laveste fælles forfader