Construct Binary Tree from Preorder and Inorder Traversal
Vous disposez de deux tableaux, preorder et inorder, qui répertorient les valeurs distinctes du même arbre binaire. Le parcours préfixe visite un nœud, puis son sous-arbre gauche, puis son sous-arbre droit. Le parcours infixe visite le sous-arbre gauche, puis le nœud, puis le sous-arbre droit.
Reconstruisez l’arbre et renvoyez-le sous forme de tableau en ordre par niveaux : la racine à l’indice 0, les enfants de l’indice i aux indices 2i+1 (gauche) et 2i+2 (droit), et -1 pour chaque emplacement vide. Le tableau se termine au dernier nœud, sans -1 final.
Fonction
- preorderinteger-array
- les valeurs en préordre : nœud, sous-arbre gauche, sous-arbre droit
- inorderinteger-array
- les valeurs dans l’ordre infixe : sous-arbre gauche, nœud, sous-arbre droit
- Renvoieinteger-array
- l’arbre dans l’ordre par niveau, avec -1 pour les emplacements vides et sans -1 final
Contraintes
1 ≤ preorder.length ≤ 3000inorder.length == preorder.length0 ≤ preorder[i] ≤ 104, et toutes les valeurs sont distinctes.inordercontient les mêmes valeurs, et les deux tableaux décrivent le même arbre binaire.- La profondeur de l’arbre est au plus
14, donc tous les indices de la réponse sont inférieurs à214-1 = 16383.
Exemples
- Entrée
- preorder = [7, 3, 0, 9, 4, 6]inorder = [0, 3, 9, 7, 4, 6]
- Sortie
- [7, 3, 4, 0, 9, -1, 6]
- Explication
- Le parcours préfixe commence par la racine,
7. Elle se trouve à la position3dansinorder, donc0, 3, 9vont à gauche et4, 6vont à droite.4n’a qu’un enfant droit,6, donc l’index5reste-1.
- Entrée
- preorder = [1, 2, 3]inorder = [2, 3, 1]
- Sortie
- [1, 2, -1, -1, 3]
- Explication
- La racine
1vient en dernier dansinorder, donc l’indice2est-1. Parmi2, 3, preorder place2en premier et inorder place3après lui, donc3est son enfant droit, à l’indice4.
Pour aller plus loin
Peux-tu reconstruire l’arbre sans récursion, en un seul parcours de preorder avec une pile explicite ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Quel tableau vous indique la racine de l’arbre entier, et où se trouve cette racine dans l’autre tableau ?
La racine sépare
inorderen valeurs du sous-arbre gauche et en valeurs du sous-arbre droit. Danspreorder, les valeurs du sous-arbre gauche viennent juste après la racine, en nombre égal à celles du côté gauche. La même séparation fonctionne dans chaque sous-arbre.Récursivez sur une plage inorder
lo..hiavec l’indice preorder de sa racine et son indice de sortieh: écrivez la racine àh, trouvez sa position inorderm, puis construisez la partie gauche à2*h+1et la partie droite à2*h+2. Une map associant chaque valeur à sa position inorder permet de trouvermen une étape.
Solution
Le parcours préfixe donne la racine de chaque sous-arbre : la première valeur de son segment. Le parcours infixe donne la séparation : les valeurs avant la racine vont à gauche, celles après vont à droite. En répétant l’opération sur les deux moitiés, on reconstruit l’arbre, et une table associant chaque valeur à sa position dans le parcours infixe permet de trouver chaque racine en une étape.
Diviser récursivement, en recherchant la racine
Intuition
En parcours préfixe, le sous-arbre gauche suit sa racine et prend une entrée par valeur, soit m-lo entrées, où m est la position de la racine dans le parcours infixe. Le sous-arbre droit vient ensuite, donc sa racine se trouve à pre+1+(m-lo). Dans le premier exemple, la partie gauche 0, 3, 9 contient trois valeurs, donc le sous-arbre droit commence à l’index 4 du parcours préfixe, avec la valeur 4.
Une profondeur d’au plus 14 maintient chaque index de sortie inférieur à 2^14-1. Remplissez autant de cases avec -1, écrivez chaque valeur à son index, puis supprimez à la fin les entrées -1 à la suite.
Parcourir chaque intervalle infixe pour y chercher sa racine coûte O(n·h) : les intervalles d’un même niveau ne se chevauchent pas, donc un niveau parcourt au plus n entrées, soit au plus 14 × 3000 = 42000 étapes ici. Sans limite de profondeur, un arbre en forme de chemin donne une complexité de O(n²).
Algorithme
- Créez
outavec2^14-1entrées, toutes égales à-1. - Écrivez
build(pre, lo, hi, h): silo > hi, retournez. Sinon, écrivezpreorder[pre]dansout[h]. - Parcourez
inorderà partir delopour trouver la positionmde la racine. Le sous-arbre gauche contientm-lovaleurs. - Appelez
build(pre+1, lo, m-1, 2*h+1)etbuild(pre+1+(m-lo), m+1, hi, 2*h+2). - Appelez
build(0, 0, n-1, 0), puis supprimez les entrées-1finales et retournez le reste.
def buildTree(preorder, inorder):
out = [-1] * (2 ** 14 - 1) # every index of a depth-14 tree is below 2^14-1
def build(pre, lo, hi, h):
# preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
# it goes to index h of the output.
if lo > hi:
return
value = preorder[pre]
out[h] = value
m = lo
while inorder[m] != value: # find the root in the inorder range
m += 1
left_size = m - lo
build(pre + 1, lo, m - 1, 2 * h + 1)
build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)
build(0, 0, len(inorder) - 1, 0)
last = len(out) - 1
while out[last] == -1: # trim the trailing -1 entries
last -= 1
return out[:last + 1]Diviser récursivement à l’aide d’une carte des positions
Intuition
Les valeurs sont distinctes, donc chacune occupe exactement une position dans inorder. Enregistrez cette position dans une table de hachage associant chaque valeur à sa position avant le début de la récursion ; chaque recherche de racine ne prend alors qu’une étape.
La construction de la table prend O(n), puis chaque valeur est placée une seule fois avec un travail constant, donc le temps total est de O(n). La table utilise un espace de O(n) et la récursion une pile par niveau. En C et R, les valeurs sont au plus égales à 10^4, donc un simple tableau de 10^4+1 entrées sert de table.
Algorithme
- Construis une map associant chaque valeur de
inorderà sa position. - Crée
outavec2^14-1entrées, toutes égales à-1. - Dans
build(pre, lo, hi, h), retourne silo > hi; sinon, écrispreorder[pre]dansout[h]et recherche sa positionmdans la map. - Fais les appels récursifs avec
build(pre+1, lo, m-1, 2*h+1)etbuild(pre+1+(m-lo), m+1, hi, 2*h+2). - Appelle
build(0, 0, n-1, 0), puis supprime les entrées-1à la fin et retourne le reste.
def buildTree(preorder, inorder):
position = {value: i for i, value in enumerate(inorder)} # value -> inorder index
out = [-1] * (2 ** 14 - 1) # every index of a depth-14 tree is below 2^14-1
def build(pre, lo, hi, h):
# preorder[pre] is the root of the subtree that inorder[lo..hi] lists;
# it goes to index h of the output.
if lo > hi:
return
value = preorder[pre]
out[h] = value
m = position[value]
left_size = m - lo
build(pre + 1, lo, m - 1, 2 * h + 1)
build(pre + 1 + left_size, m + 1, hi, 2 * h + 2)
build(0, 0, len(inorder) - 1, 0)
last = len(out) - 1
while out[last] == -1: # trim the trailing -1 entries
last -= 1
return out[:last + 1]
Pièges et cas limites
- Commencer le sous-arbre droit à
pre+1+mau lieu depre+1+(m-lo). Cela fonctionne lorsquelovaut0, comme lors de l’appel initial, et échoue dès qu’une plage commence plus loin. - Supprimer les trous. Un enfant manquant conserve tout de même sa place, donc le deuxième exemple renvoie
[1, 2, -1, -1, 3], et non[1, 2, 3]. - Conserver les entrées
-1finales. Renvoyer les2^14-1cases donne au premier exemple 16376 entrées-1supplémentaires. - Copier des tranches des deux tableaux à chaque appel, ce qui ajoute
O(n)par niveau. Passe des plages d’indices. - En Lua et en R, les tableaux commencent à 1. Garde les positions indexées à partir de 0 pour les calculs et lis
preorder[pre + 1]etout[h + 1].
Questions fréquentes3
Pourquoi avez-vous besoin des parcours préfixe et infixe pour reconstruire un arbre binaire ?
Le parcours préfixe à lui seul ne détermine pas la forme. Le parcours préfixe [1, 2] correspond à un arbre où 2 est le fils gauche de 1, ainsi qu’à un arbre où il en est le fils droit. Le parcours infixe permet de trancher : [2, 1] place 2 à gauche, [1, 2] à droite. Avec des valeurs distinctes, la paire décrit un seul arbre.
Quelle est la complexité temporelle de la construction d’un arbre binaire à partir des parcours préfixe et infixe ?
Avec une correspondance entre les valeurs et leur position dans le parcours infixe, la complexité est de O(n) en temps et de O(n) en espace supplémentaire. Sans cette correspondance, parcourir chaque plage du parcours infixe pour trouver sa racine coûte O(n·h), ce qui devient O(n²) pour un arbre en forme de chemin.
Peux-tu reconstruire un arbre binaire à partir de son parcours préfixe et de son parcours postfixe ?
Pas en général. Le parcours préfixe [1, 2] et le parcours postfixe [2, 1] correspondent aussi bien à un enfant gauche qu’à un enfant droit, car aucun des deux parcours ne place la racine entre ses sous-arbres. Cette paire suffit uniquement pour un arbre binaire strict, où chaque nœud a zéro ou deux enfants.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def buildTree(preorder, inorder):
# Écrivez le code iciTest #1
Test #2
Arguments
preorder = [7, 3, 0, 9, 4, 6] inorder = [0, 3, 9, 7, 4, 6]
Résultat attendu
[7, 3, 4, 0, 9, -1, 6]