Comment trouver la profondeur maximale d'un arbre binaire en Java (avec code)

Le contenu de cet article explique comment trouver la profondeur maximale d'un arbre binaire en Java (avec du code). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

Étant donné un arbre binaire, trouver sa profondeur maximale.

La profondeur d'un arbre binaire est le nombre de nœuds sur le chemin le plus long depuis le nœud racine jusqu'au nœud feuille le plus éloigné.

Explication : Un nœud feuille fait référence à un nœud qui n'a pas de nœuds enfants.

Exemple :
Étant donné un arbre binaire [3,9,20,null,null,15,7],

3
/
9 20
/
15 7

Renvoie sa profondeur maximale de 3.

Maîtriser l'utilisation des arbres à travers cette question

Analyse de la question : Trouver la profondeur d'un arbre binaire

Vous pouvez parcourir Aperçu des concepts de base des arbres binaires pour mieux comprendre les arbres binaires

Nous utilisons également la méthode récursive pour résoudre ce problème ; . Le nœud racine n'est pas vide, nous parcourons récursivement le sous-arbre gauche et le sous-arbre droit pour voir quel sous-arbre a le plus de niveaux, et enfin parcourons jusqu'à atteindre le nœud feuille

Utiliser un La mise en œuvre technique de l'instruction : return nleft > nright nleft + 1 : nright + 1;

Avec cet arbre Prenons comme exemple un arbre binaire :

3

/
9 20
/
15 7

1 . Cet arbre n'est pas vide

2. Parcourez récursivement le sous-arbre gauche de cet arbre : le sous-arbre gauche n'est pas vide si le sous-arbre gauche et le sous-arbre droit du sous-arbre gauche sont tous deux vides. vide, 0 sera renvoyé pour jugement, 0 == 0, le sous-arbre gauche de cet arbre renvoie 0 + 1 = 1 ;

3. le sous-arbre droit n'est pas vide ;droit Le sous-arbre gauche et le sous-arbre droit du sous-arbre ne sont pas vides ; le sous-arbre droit est vide, renvoie 0, le sous-arbre gauche et le sous-arbre droit du sous-arbre droit du sous-arbre droit sont vides, renvoie 0, porte un jugement, 0 == 0, puis le sous-arbre gauche et le sous-arbre droit du sous-arbre droit de cet arbre renvoie 0 + 1 = 1, jugez 1 == 1, puis le sous-arbre droit de cet arbre renvoie 1 + 1 = 2

4. sous-arbre, 1 < 2, alors cet arbre renvoie 2 + 1 = 3, alors la profondeur de cet arbre, c'est-à-dire le nombre de couches, est de 3.

En fait, l'idée principale de cette méthode est la suivante : tant que vous parcourez récursivement jusqu'aux nœuds feuilles de cet arbre, enfin, revenez simplement des nœuds feuilles au nœud racine et +1. Le résultat est la longueur. du chemin renvoyé +1.

Implémentation du code :

public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int val)
        {
            data = val;
        }
    }

    public int maxDepth(TreeNode root)
    {
        if (root == null)
            return 0;

        int nleft = maxDepth(root.left);
        int nright = maxDepth(root.right);

        return nleft > nright ? nleft + 1 : nright + 1;
    }

Fonction principale :

public static void main(String[] args)
    {
        TreeNode p = new TreeNode(1);
        p.left = new TreeNode(2);
        p.right = new TreeNode(3);
        p.left.left = null;
        p.left.right = null;
        p.right.left = new TreeNode(4);
        p.right.right = new TreeNode(5);

        Tree1 t = new Tree1();
        System.out.println(t.maxDepth(p));
    }

Résultat d'exécution : 3

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!