Boundary Traversal of Binary Tree
L’array root contiene un albero binario in ordine per livelli: la radice all’indice 0, i figli dell’indice i agli indici 2i+1 (sinistro) e 2i+2 (destro), -1 per una posizione vuota e, eventualmente, ulteriori elementi -1 alla fine. Una foglia è un nodo senza figli.
Restituisci il contorno in senso antiorario a partire dalla radice:
- La radice.
- Il contorno sinistro, dall’alto verso il basso: partendo dal figlio sinistro della radice, prosegui con il figlio sinistro, se presente; altrimenti, con il figlio destro. Fermati prima di una foglia.
- Tutte le foglie, da sinistra a destra.
- Il contorno destro, dal basso verso l’alto: il contrario di quello sinistro, partendo dal figlio destro della radice.
Nessun nodo viene elencato due volte, quindi un albero con un solo nodo restituisce soltanto la radice.
Funzione
- rootinteger-array
- l’albero binario in ordine di livello, con -1 per una posizione vuota
- Restituisceinteger-array
- i valori limite, in senso antiorario a partire dalla radice
Vincoli
1 ≤ root.length ≤ 32767- Ogni
root[i]è-1oppure un valore con0 ≤ root[i] ≤ 105. root[0]non è mai-1, quindi l’albero ha almeno un nodo.- L'array può terminare con voci
-1aggiuntive dopo l'ultimo nodo. - Entrambi i figli di un punto vuoto sono vuoti anch’essi e la profondità è al massimo
14. - I valori dei nodi sono distinti.
Esempi
- Input
- root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
- Output
- [7, 3, 1, 4, 6, 8, 9]
- Spiegazione
- Dopo la radice
7, il confine sinistro è3: il suo figlio1è una foglia. Le foglie sono1,4,6,8. Il confine destro è9, sopra la foglia8.
- Input
- root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
- Output
- [10, 4, 6, 5, 8]
- Spiegazione
4non ha un figlio sinistro, quindi il confine sinistro passa a6, poi si ferma alla foglia5. Seguono le foglie5,8. La radice non ha un figlio destro.
- Input
- root = [3]
- Output
- [3]
- Spiegazione
- La radice è l'intero albero. Viene elencata una sola volta, non di nuovo come foglia.
Per approfondire
Come elencheresti il contorno in senso orario: la radice, il bordo destro dall’alto verso il basso, le foglie da destra a sinistra, poi il bordo sinistro dal basso verso l’alto?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Suddividi la risposta in quattro parti: la radice, il bordo sinistro, le foglie e il bordo destro. Quali di queste sono un singolo percorso lungo l’albero e quali richiedono una visita completa?
Ogni arco è un percorso: dal figlio della radice, continua a spostarti verso il figlio da quel lato oppure verso l’altro figlio quando quel lato è vuoto. Le foglie, nell’ordine da sinistra a destra, si ottengono con una visita in profondità che visita prima il sottoalbero sinistro. Fai attenzione ai punti di giunzione: la foglia in cui termina un arco appartiene alle foglie.
Procedi verso il basso dall’indice
1e aggiungi ogni nodo non foglia. Poi aggiungi ogni foglia con una visita in preordine. Poi procedi verso il basso dall’indice2, raccogli ogni nodo non foglia e aggiungi l’elenco in ordine inverso.
Soluzione
La risposta unisce quattro parti: la radice, un percorso lungo il bordo sinistro, le foglie da sinistra a destra e un percorso lungo il bordo destro letto al contrario. Nei punti di unione, una foglia che conclude un bordo e una radice che è una foglia devono essere elencate una sola volta.
Cammina separatamente le tre parti
Intuizione
Ogni bordo è un percorso: dal figlio della radice, elenca i nodi finché il successivo non sarebbe una foglia, che viene invece elencata nella parte delle foglie. Una visita in preordine che procede prima a sinistra e poi a destra incontra le foglie da sinistra a destra, perché ogni nodo di un sottoalbero sinistro si trova a sinistra del sottoalbero destro, indipendentemente dalla sua profondità. Raccogli il bordo destro dall’alto verso il basso e aggiungilo al contrario.
Ogni bordo segue un solo percorso e la visita delle foglie visita ogni nodo una volta: tempo O(n), con la ricorsione profonda h livelli.
Algoritmo
- Inizia dalla radice; se è una foglia, restituiscila.
- Dall'indice
1, finché il nodo esiste e non è una foglia, aggiungilo e passa al suo figlio sinistro, oppure al figlio destro se non c'è quello sinistro. - Percorri in preordine, dando la precedenza a sinistra, dagli indici
1e2, aggiungendo ogni foglia. - Dall'indice
2, fai lo stesso del passaggio 2 dando la precedenza ai figli destri e raccogliendo i nodi. - Aggiungi i nodi raccolti in ordine inverso.
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
def is_leaf(i):
return not real(2 * i + 1) and not real(2 * i + 2)
result = [root[0]]
if is_leaf(0):
return result
# 1. The left boundary, top-down, stopping before its leaf.
i = 1
while real(i) and not is_leaf(i):
result.append(root[i])
i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2
# 2. Every leaf: a pre-order walk meets them from left to right.
def add_leaves(i):
if not real(i):
return
if is_leaf(i):
result.append(root[i])
return
add_leaves(2 * i + 1)
add_leaves(2 * i + 2)
add_leaves(1)
add_leaves(2)
# 3. The right boundary, collected top-down and added bottom-up.
right = []
i = 2
while real(i) and not is_leaf(i):
right.append(root[i])
i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
result.extend(reversed(right))
return resultUn passaggio di preordine con flag sui bordi
Intuizione
Riunisci le visite in un'unica scansione in preordine su uno stack assegnando a ogni nodo un flag: 1 sul bordo sinistro, 2 sul bordo destro, 0 all'interno. I figli della radice iniziano con 1 e 2. Un nodo sul bordo passa il proprio flag al figlio dal suo lato, oppure al suo unico figlio; ogni altro figlio riceve 0. Nel secondo esempio, il 1 passa da 4 a 6 a 5.
Man mano che i nodi escono dallo stack, aggiungi ogni foglia e ogni nodo non foglia contrassegnato con 1; raccogli i nodi non foglia contrassegnati con 2 e aggiungili in ordine inverso alla fine. La visita in preordine raggiunge ogni nodo del bordo sinistro prima di qualsiasi foglia, perché il bordo svolta a destra solo dove non c'è nulla alla sua sinistra.
Algoritmo
- Inizia dalla radice. Inserisci il figlio destro con il contrassegno
2, poi il figlio sinistro con il contrassegno1. - Estrai un nodo. Aggiungilo se è una foglia o ha il contrassegno
1; aggiungi un nodo non foglia con il contrassegno2all’elenco di destra. - Inserisci il figlio destro, poi quello sinistro, ciascuno con il contrassegno assegnatogli dalla regola.
- Quando la pila è vuota, aggiungi l’elenco di destra in ordine inverso.
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
result = [root[0]]
right = [] # the right boundary, top-down; it goes on the end reversed
# Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
stack = []
if real(2):
stack.append((2, 2))
if real(1):
stack.append((1, 1))
while stack:
i, edge = stack.pop()
has_left, has_right = real(2 * i + 1), real(2 * i + 2)
if not has_left and not has_right:
result.append(root[i]) # a leaf; pre-order meets them left to right
elif edge == 1:
result.append(root[i]) # the left boundary, top-down
elif edge == 2:
right.append(root[i])
# An edge passes to the child on its own side, or to an only child.
# The right child goes on the stack first, so the left one comes out first.
if has_right:
stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
if has_left:
stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
result.extend(reversed(right))
return result
Trappole e casi limite
- Elencare un nodo due volte. Un percorso lungo gli archi che non si ferma prima della foglia elenca
1due volte nell'esempio 1, e un albero con un solo nodo non deve elencare di nuovo la radice come foglia. - Considerare il primo nodo di ogni livello come limite sinistro. Se il figlio sinistro della radice è una foglia e il sottoalbero destro è più profondo, i livelli più profondi iniziano con nodi del sottoalbero destro, eppure il limite sinistro è vuoto.
- Seguire solo i figli sinistri. Nell'esempio 2, il limite deve andare da
4al suo figlio destro6. - Raccogliere le foglie livello per livello. L'esempio 1 restituisce quindi
1,8,4,6. - In Lua e R, mantieni gli indici dei nodi a base 0 per l'aritmetica
2i+1e leggiroot[i + 1].
Domande frequenti3
Che cos'è la visita del contorno di un albero binario?
Elenca il contorno dell'albero in senso antiorario: la radice, il bordo sinistro dall'alto verso il basso, le foglie da sinistra a destra e il bordo destro dal basso verso l'alto. I bordi escludono le foglie, quindi nessun nodo appare due volte.
Qual è la complessità temporale della visita del perimetro?
O(n). Le due percorrenze dei bordi seguono ciascuna un percorso, e la percorrenza delle foglie visita ogni nodo una volta. Lo spazio aggiuntivo è O(h) per la ricorsione o lo stack.
Il confine sinistro segue sempre i figli a sinistra?
No. Si sposta al figlio sinistro, se presente, e altrimenti al figlio destro: il percorso più esterno che vedi da sinistra. Se la radice non ha un figlio sinistro, il confine sinistro è vuoto.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def boundaryTraversal(root):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
Output atteso
[7, 3, 1, 4, 6, 8, 9]