Différents arbres de recherche binaires [arbre de génération rétrospectif ascendant + recherche de mémoire - - espace - temps]

Préface

Premièrement,Pour la génération d'arbres binaires,Détermination récursive descendante des intervalles de sous - arbres,Arbre de génération d'épissage descendant.
Deuxièmement,Pour beaucoup de calculs répétés,Les résultats peuvent être mémorisés avec un espace supplémentaire,Je le récupérerai quand je le rencontrerai plus tard.,Réduire considérablement la complexité temporelle,En général, c'est la complexité exponentielle.,Cela est particulièrement nécessaire.

Un.、Différents arbres de recherche binaires

2.、Arbre de construction+Recherche de mémoire

1、Génération d'arbres binaires par rétrotraçage récursif

// Différents arbres de recherche binaires.
public class NumTrees {
    
    /* target：Nombre de noeuds donnés,Renvoie le nombre de différents arbres de recherche binaires. Noeud racine par noeud,La multiplication du nombre de sous - arbres gauche et droit est le nombre de différents arbres binaires. De bas en haut,Arbre rétrospectif. */
    public int numTrees(int n) {
    
        return numTrees(1, n);
    }

    // De bas en haut,Génération rétrospective.
    private int numTrees(int begin, int end) {
    
        // Impossible de diviser à nouveau,Nombre d'enfants retournés à gauche,1- Oui.nullNoeud.
        if (begin > end) return 1;
        //  Obtenez le nombre de combinaisons d'enfants de gauche et de droite .
        int rs = 0;
        for (int i = begin; i <= end; i++) {
    
            // iComme noeud racine,Diviser en deux sections, Comme sous - arbres de gauche et de droite .
            rs += numTrees(begin, i - 1) * numTrees(i + 1, end);
        }
        return rs;
    }
}

2、Recherche de mémoire–Espace contre temps

//  Le scénario ci - dessus a expiré , Si vous obtenez simplement un nombre différent d'arbres binaires , Il n'est pas nécessaire de simuler chaque   L'intervalle génère un sous - arbre , Enregistrer après la première génération , On se retrouve dans cette section , Valeur directe .
class NumTrees2 {
    
    /* target：Nombre de noeuds donnés,Renvoie le nombre de différents arbres de recherche binaires. Noeud racine par noeud,La multiplication du nombre de sous - arbres gauche et droit est le nombre de différents arbres binaires. De bas en haut,Arbre rétrospectif. Espace contre temps,Définitionf[i][j]:[i,j] Combien de sous - arbres sont possibles , L'affectation est calculée pour la première fois , Si on se croise plus tard, on n'a pas à oublier , Retirer directement pour . */
    public int numTrees(int n) {
    
        // Définition[i,j] Combien de sous - arbres peuvent être générés .
        int[][] f = new int[n + 1][n + 1];
        // De bas en haut,Génération rétrospective.
        return numTrees(1, n, f);
    }

    // De bas en haut,Génération rétrospective.
    private int numTrees(int begin, int end, int[][] f) {
    
        // Impossible de diviser à nouveau,Nombre d'enfants retournés à gauche,1- Oui.nullNoeud.
        if (begin > end) return 1;
        // Recherche de mémoire
        if (f[begin][end] != 0) return f[begin][end];
        //  Obtenez le nombre de combinaisons d'enfants de gauche et de droite .
        //  La première fois que je touche cette section , Et les résultats qu'il a obtenus, rappelez - vous .
        for (int i = begin; i <= end; i++) {
    
            // iComme noeud racine,Diviser en deux sections, Comme sous - arbres de gauche et de droite .
            f[begin][end] += numTrees(begin, i - 1, f) * numTrees(i + 1, end, f);
        }
        //  Renvoie le nombre de sous - arbres calculés pour la première fois dans cet intervalle .
        return f[begin][end];
    }
}

Résumé

1） Comment faire un arbre binaire , Diviser Récursivement les intervalles de gauche et de droite de haut en bas , De bas en haut, les sous - arbres gauche et droit .
2） La recherche de mémoire est utilisée pour éviter le double comptage ,Réduire la complexité temporelle, En particulier, la complexité exponentielle du temps .

Références

[1] LeetCode Différents arbres de recherche binaires