So ermitteln Sie die maximale Tiefe eines Binärbaums in Java (mit Code)

Der Inhalt dieses Artikels handelt davon, wie man die maximale Tiefe eines Binärbaums in Java ermittelt (mit Code). Ich hoffe, dass er für Sie hilfreich ist.

Bestimmen Sie bei einem gegebenen Binärbaum dessen maximale Tiefe.

Die Tiefe eines Binärbaums ist die Anzahl der Knoten auf dem längsten Pfad vom Wurzelknoten zum am weitesten entfernten Blattknoten.

Erklärung: Ein Blattknoten bezieht sich auf einen Knoten, der keine untergeordneten Knoten hat.

Beispiel:
Gegeben ein Binärbaum [3,9,20,null,null,15,7],

3
/
9 20
/
15 7

Gibt die maximale Tiefe von 3 zurück.

Meistern Sie die Verwendung von Bäumen durch diese Frage

Fragenanalyse: Finden Sie die Tiefe eines Binärbaums; 🎜>Sie können

Übersicht über die Grundkonzepte von Binärbäumen

durchsuchen, um Binärbäume besser zu verstehen Wir verwenden auch die rekursive Methode, um dieses Problem zu lösen . Der Wurzelknoten ist nicht leer, wir durchlaufen rekursiv den linken Teilbaum und den rechten Teilbaum, um zu sehen, welcher Teilbaum mehr Ebenen hat, und durchlaufen ihn schließlich, bis wir den Blattknoten erreichen >Verwenden Sie eine technische Implementierung der Anweisung:

return nleft > nright + 1;

Mit diesem Baum Nehmen Sie als Beispiel einen Binärbaum: 3 / 9 20

/

15 7

1. Dieser Baum ist nicht leer

2. Durchlaufen Sie den linken Teilbaum rekursiv: Der linke Teilbaum ist nicht leer; , 0 wird zur Beurteilung zurückgegeben, 0 == 0, der linke Teilbaum dieses Baums gibt 0 + 1 = 1 zurück;

3. Durchlaufen Sie rekursiv den rechten Teilbaum dieses Baums Der rechte Teilbaum ist nicht leer. Der linke Teilbaum und der rechte Teilbaum des rechten Teilbaums sind nicht leer Der rechte Teilbaum ist leer, es wird 0 zurückgegeben, der linke Teilbaum und der rechte Teilbaum des rechten Teilbaums sind leer, es wird 0 zurückgegeben, ein Urteil fällt, 0 == 0, dann sind der linke Teilbaum und der rechte Teilbaum des rechten Teilbaums davon Baum gibt 0 + 1 = 1 zurück, Richter 1 == 1, dann gibt der rechte Teilbaum dieses Baums 1 + 1 = 2 zurück

4 , 1 < 2, dann gibt dieser Baum 2 + 1 = 3 zurück, dann beträgt die Tiefe dieses Baums, also die Anzahl der Schichten, 3.

In Tatsächlich besteht die Hauptidee dieser Methode darin, den gesamten Weg bis zu den Blattknoten dieses Baums zu durchlaufen und schließlich die Länge von +1 zu erhöhen der Pfad hat +1 zurückgegeben.

Code-Implementierung:

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;
    }

Hauptfunktion:

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));
    }

Laufergebnis: 3

Das obige ist der detaillierte Inhalt vonSo ermitteln Sie die maximale Tiefe eines Binärbaums in Java (mit Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!