Subtree of Another Tree

Q: Quelle est la complexité temporelle de Subtree of Another Tree ?

Comparer à partir de chaque nœud coûte O(n·m) dans le pire des cas, où n et m sont les tailles des deux arbres. Comparer uniquement aux nœuds dont la hauteur est égale à celle de subRoot ramène cette complexité à O(n + m) , car chaque nœud de root est alors parcouru au plus une fois.

Q: Peut-on résoudre le problème « Sous-arbre d'un autre arbre » avec la recherche de chaînes ?

Oui. Écris chaque arbre en parcours préfixe avec # pour chaque enfant vide et un séparateur avant chaque valeur : ,2,1,#,#,3,#,# . subRoot est un sous-arbre exactement lorsque sa chaîne apparaît dans la chaîne de root , et KMP le trouve en O(n + m) . Sans les marqueurs, différentes formes donnent la même chaîne ; sans séparateurs, 12 contient 2 .

FacileParcours d’arbre Récursivité

+10

Vous recevez deux arbres binaires, root et subRoot, chacun stocké dans un tableau en parcours par niveaux : la racine à l’index 0, les enfants de l’index i aux index 2*i+1 (à gauche) et 2*i+2 (à droite), et -1 pour un emplacement vide. Un tableau peut se terminer par des entrées -1 supplémentaires.

Renvoyez true si un nœud de root, avec tous ses descendants, a exactement la même forme et les mêmes valeurs que subRoot, et false dans le cas contraire. L’arbre entier root compte également.

Fonction

isSubtree(root: integer-array, subRoot: integer-array) → boolean

rootinteger-array: l’arbre dans lequel effectuer la recherche, en parcours par niveaux, avec -1 pour une position vide
subRootinteger-array: l’arbre à rechercher, dans le même format
Renvoieboolean: vrai si subRoot apparaît dans root comme un nœud avec tous ses descendants, faux sinon

Contraintes

1 ≤ root.length ≤ 32767 et 1 ≤ subRoot.length ≤ 32767
Chaque entrée est -1 ou une valeur comprise entre 0 et 10⁴.
root[0] et subRoot[0] ne sont jamais -1, donc les deux arbres ont au moins un nœud.
L’un ou l’autre tableau peut se terminer par des entrées -1 supplémentaires après son dernier nœud.
Les deux enfants d’un emplacement vide sont également vides, et chaque arbre a une profondeur d’au plus 14.
Les valeurs peuvent se répéter.

Exemples

Entrée: root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
Sortie: true
Explication: Le nœud 2 à l’indice 1 a pour enfants 1 et 3, et tous deux sont des feuilles. C’est exactement subRoot.

Entrée: root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
Sortie: false
Explication: Le 3 sous le nœud 2 a maintenant un enfant 0. Un sous-arbre comprend tous ses descendants, donc le nœud 2 compte quatre nœuds contre les trois de subRoot, et aucun autre nœud ne contient de 2.

Entrée: root = [5, 5, 7]subRoot = [5]
Sortie: true
Explication: La racine 5 a deux enfants, donc elle ne correspond pas au nœud unique 5. Le 5 à l’indice 1 est une feuille et correspond.

Pour aller plus loin

Peux-tu attribuer une empreinte à chaque sous-arbre à partir de sa valeur et des empreintes de ses enfants, de sorte qu’une comparaison avec subRoot coûte O(1) ? Que fais-tu lorsque deux sous-arbres différents entrent en collision ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Le problème comporte deux parties : déterminer si deux arbres sont identiques et choisir où, dans root, effectuer cette vérification. Seul un nœud dont la hauteur est égale à celle de subRoot peut correspondre, et les nœuds d’une même hauteur ne se chevauchent jamais ; ainsi, en ne vérifiant que ceux-ci, on parcourt chaque nœud de root au plus une fois.

Comparer à chaque nœud

Intuition

Un emplacement i est réel lorsque i se trouve dans le tableau et que la valeur à cet emplacement n’est pas -1. Deux arbres sont identiques lorsqu’ils sont tous deux vides, ou lorsque leurs racines contiennent la même valeur et que leurs sous-arbres gauche et droit sont identiques. same(i, j) parcourt root à partir de i et subRoot à partir de j, pas à pas. Si subRoot apparaît dans root, sa racine se trouve sur un nœud ; essayez donc same(i, 0) à partir de chaque i réel.

Une correspondance presque exacte peut durer jusqu’à m étapes avant d’échouer, pour chacun des n nœuds : O(n·m). Ici, la limite de profondeur réduit ce coût : un nœud n’est parcouru que par les vérifications qui commencent à ce nœud ou au-dessus, au maximum 14.

Algorithme

Écrivez same(i, j). Si la position i dans root et la position j dans subRoot sont toutes deux vides, renvoyez true ; si une seule l’est, renvoyez false.
Si les deux valeurs diffèrent, renvoyez false. Sinon, renvoyez same(2*i+1, 2*j+1) et same(2*i+2, 2*j+2).
Renvoyez true si same(i, 0) est vérifiée pour un indice existant i de root, et false sinon.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    # Try every real node of root as the top of a match.
    for i in range(n):
        if root[i] != -1 and same(i, 0):
            return True
    return False

Comparez uniquement lorsque les hauteurs correspondent

Intuition

Des arbres identiques ont la même hauteur, comptée comme le nombre de nœuds sur le plus long chemin vers le bas. Il vaut donc la peine de vérifier uniquement les nœuds de root dont la hauteur est égale à celle de subRoot. Dans le premier exemple, subRoot a une hauteur de 2, et seuls 2 et 8 dans root ont cette hauteur.

Un nœud est plus haut que tous les nœuds situés en dessous de lui, donc deux nœuds de même hauteur ne peuvent jamais se trouver l’un à l’intérieur de l’autre. Chaque vérification parcourt uniquement le sous-arbre de son nœud de départ ; ensemble, les vérifications parcourent donc chaque nœud de root au plus une fois.

Les enfants se trouvent à des index plus élevés que leur parent, donc un parcours des index en ordre décroissant atteint les deux enfants avant le parent. Les deux calculs de hauteur et les vérifications prennent un temps de O(n + m).

Algorithme

Remplis un tableau des hauteurs pour chaque arbre, en parcourant les indices du dernier jusqu’à 0 : une case vide reçoit 0, un nœud réel reçoit 1 plus la plus grande hauteur de ses deux enfants.
Pour chaque indice i de root dont la hauteur est égale à la hauteur à l’indice 0 de subRoot, exécute same(i, 0) et renvoie true si c’est le cas.
Renvoie false.

def isSubtree(root, subRoot):
    n, m = len(root), len(subRoot)

    def same(i, j):
        # True if the subtree at root[i] equals the subtree at subRoot[j].
        a = i < n and root[i] != -1
        b = j < m and subRoot[j] != -1
        if not a or not b:
            return a == b  # two empty spots match, one empty spot does not
        if root[i] != subRoot[j]:
            return False
        return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)

    def heights(tree):
        # Children sit at larger indexes, so a backward scan finishes them first.
        h = [0] * len(tree)
        for i in range(len(tree) - 1, -1, -1):
            if tree[i] != -1:
                left = h[2 * i + 1] if 2 * i + 1 < len(tree) else 0
                right = h[2 * i + 2] if 2 * i + 2 < len(tree) else 0
                h[i] = 1 + max(left, right)
        return h

    target = heights(subRoot)[0]
    rootHeights = heights(root)
    # Only a node of the same height can match, and no two such nodes overlap.
    for i in range(n):
        if rootHeights[i] == target and same(i, 0):
            return True
    return False

Pièges et cas limites

Accepter une correspondance partielle, comme dans le deuxième exemple. same doit échouer lorsque root contient un nœud à un emplacement où subRoot a un emplacement vide.
S’arrêter au premier nœud ayant la bonne valeur. Dans le troisième exemple, la racine 5 échoue et la feuille 5 située en dessous correspond.
Comparer des tranches des deux tableaux. Les nœuds d’un sous-arbre sont répartis sur de nombreux niveaux, et l’un ou l’autre tableau peut se terminer par des entrées -1 supplémentaires. Un index au-delà de la fin correspond à un emplacement vide, comme un -1.
En Lua et en R, conserver des index de nœuds commençant à 0 pour le calcul 2*i+1 et lire root[i + 1].

Questions fréquentes3

Quelle est la complexité temporelle de Subtree of Another Tree ?

Comparer à partir de chaque nœud coûte O(n·m) dans le pire des cas, où n et m sont les tailles des deux arbres. Comparer uniquement aux nœuds dont la hauteur est égale à celle de subRoot ramène cette complexité à O(n + m), car chaque nœud de root est alors parcouru au plus une fois.

Peut-on résoudre le problème « Sous-arbre d'un autre arbre » avec la recherche de chaînes ?

Oui. Écris chaque arbre en parcours préfixe avec # pour chaque enfant vide et un séparateur avant chaque valeur : ,2,1,#,#,3,#,#. subRoot est un sous-arbre exactement lorsque sa chaîne apparaît dans la chaîne de root, et KMP le trouve en O(n + m). Sans les marqueurs, différentes formes donnent la même chaîne ; sans séparateurs, 12 contient 2.

Un nœud qui correspond à subRoot mais qui a des enfants supplémentaires compte-t-il ?

Non. Un sous-arbre est un nœud avec tous ses descendants ; ainsi, chaque nœud sous la correspondance doit également apparaître dans subRoot. Dans le deuxième exemple, le 0 supplémentaire sous le 3 rend la réponse false.

def isSubtree(root, subRoot):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

root = [6, 2, 8, 1, 3, -1, 9]
subRoot = [2, 1, 3]

Résultat attendu

true