Mając dane drzewo binarne, zadaniem jest znalezienie wysokości drzewa. Wysokość drzewa to liczba wierzchołków drzewa od korzenia do najgłębszego węzła.

Notatka: Wysokość pustego drzewa wynosi 0 a wysokość drzewa z pojedynczym węzłem wynosi 1 .

Przykład drzewa binarnego

Rekurencyjnie oblicz wysokość lewy i Prawidłowy poddrzewa węzła i przypisz wysokość do węzła jako max wzrostu dwójki dzieci plus 1 . Aby uzyskać szczegółowe informacje, zobacz poniżej pseudokod i program.

Ilustracja:

Rozważmy następujące drzewo:

Przykład drzewa

maxDepth(‚1’) = max(maxDepth(‚2’), maxDepth(‚3’)) + 1 = 2 + 1

bo rekurencyjnie
maxDepth(‚2’) = max (maxDepth(‚4’), maxDepth(‚5’)) + 1 = 1 + 1 i (ponieważ wysokość zarówno „4”, jak i „5” wynosi 1)
maxDepth(‚3’) = 1

Wykonaj poniższe kroki, aby wdrożyć pomysł:

• Rekurencyjnie wykonaj wyszukiwanie w głąb.
• Jeśli drzewo jest puste, zwróć 0
• W przeciwnym razie wykonaj następujące czynności
  • Uzyskaj rekurencyjnie maksymalną głębokość lewego poddrzewa, tj. wywołaj maxDepth( drzewo->lewe poddrzewo)
  • Uzyskaj rekurencyjnie maksymalną głębokość prawego poddrzewa, tj. wywołaj maxDepth( drzewo->prawe poddrzewo)
  • Uzyskaj maksymalną maksymalną głębokość lewy I Prawidłowy poddrzewa i dodaj 1 do niego dla bieżącego węzła.
    • 
• Zwróć maksymalną głębokość.

Poniżej znajduje się implementacja powyższego podejścia:

C++

C

Jawa

Python3

C#

JavaScript

Height of tree is 3 

Złożoność czasowa: O(N) (Proszę zobaczyć post na Przejście przez drzewo dla szczegółów)
Przestrzeń pomocnicza: O(N) ze względu na stos rekurencyjny.

Znajdź maksymalną głębokość lub wysokość drzewa za pomocą Przechodzenie przez poziom zamówienia :

Do Przechodzenie przez poziom zamówienia , dodając węzły na każdym poziomie do Wykonaj poniższe kroki, aby wdrożyć pomysł:

• Przemierzaj drzewo w kolejności poziomów, zaczynając od źródło .
  • Zainicjuj pustą kolejkę Q , zmienna głębokość i pchnij źródło , a następnie naciśnij zero w Q .
  • Uruchom pętlę while do Q nie jest pusty.
    • Przechowuj przedni element Q i Wysuń przedni element.
    • Jeśli z przodu Q Jest ZERO następnie zwiększaj głębokość o jeden i jeśli kolejka nie jest pusta, naciśnij ZERO w Q .
    • Inaczej, jeśli element nie jest ZERO następnie sprawdź lewy I Prawidłowy dzieci, a jeśli tak nie jest ZERO wepchnij je Q .
• Powrót głębokość .

Poniżej znajduje się implementacja powyższego podejścia:

C++

#include> #include> using> namespace> std;> // A Tree node> struct> Node {> > int> key;> > struct> Node *left, *right;> };> // Utility function to create a new node> Node* newNode(> int> key)> {> > Node* temp => new> Node;> > temp->klucz = klucz;> > temp->lewy = temp->prawy = NULL;> > return> (temp);> }> /*Function to find the height(depth) of the tree*/> int> height(> struct> Node* root)> {> > // Initialising a variable to count the> > // height of tree> > int> depth = 0;> > queue q;> > // Pushing first level element along with NULL> > q.push(root);> > q.push(NULL);> > while> (!q.empty()) {> > Node* temp = q.front();> > q.pop();> > // When NULL encountered, increment the value> > if> (temp == NULL) {> > depth++;> > }> > // If NULL not encountered, keep moving> > if> (temp != NULL) {> > if> (temp->po lewej) {> > q.push(temp->lewo);> > }> > if> (temp->po prawej) {> > q.push(temp->prawda);> > }> > }> > // If queue still have elements left,> > // push NULL again to the queue.> > else> if> (!q.empty()) {> > q.push(NULL);> > }> > }> > return> depth;> }> // Driver program> int> main()> {> > // Let us create Binary Tree shown in above example> > Node* root = newNode(1);> > root->lewy = nowyWęzeł(2);> > root->prawo = nowyWęzeł(3);> > root->lewy->lewy = nowyWęzeł(4);> > root->lewy->prawy = nowyWęzeł(5);> > cout < <> 'Height(Depth) of tree is: '> < < height(root);> }>

Jawa

// Java program for above approach> import> java.util.LinkedList;> import> java.util.Queue;> class> GFG {> > // A tree node structure> > static> class> Node {> > int> key;> > Node left;> > Node right;> > }> > // Utility function to create> > // a new node> > static> Node newNode(> int> key)> > {> > Node temp => new> Node();> > temp.key = key;> > temp.left = temp.right => null> ;> > return> temp;> > }> > /*Function to find the height(depth) of the tree*/> > public> static> int> height(Node root)> > {> > // Initialising a variable to count the> > // height of tree> > int> depth => 0> ;> > Queue q => new> LinkedList();> > // Pushing first level element along with null> > q.add(root);> > q.add(> null> );> > while> (!q.isEmpty()) {> > Node temp = q.peek();> > q.remove();> > // When null encountered, increment the value> > if> (temp ==> null> ) {> > depth++;> > }> > // If null not encountered, keep moving> > if> (temp !=> null> ) {> > if> (temp.left !=> null> ) {> > q.add(temp.left);> > }> > if> (temp.right !=> null> ) {> > q.add(temp.right);> > }> > }> > // If queue still have elements left,> > // push null again to the queue.> > else> if> (!q.isEmpty()) {> > q.add(> null> );> > }> > }> > return> depth;> > }> > // Driver Code> > public> static> void> main(String args[])> > {> > Node root = newNode(> 1> );> > root.left = newNode(> 2> );> > root.right = newNode(> 3> );> > root.left.left = newNode(> 4> );> > root.left.right = newNode(> 5> );> > System.out.println(> 'Height(Depth) of tree is: '> > + height(root));> > }> }> // This code is contributed by jana_sayantan.>

Python3

# Python code to implement the approach> # A Tree node> class> Node:> > def> __init__(> self> ):> > self> .key> => 0> > self> .left,> self> .right> => None> ,> None> # Utility function to create a new node> def> newNode(key):> > temp> => Node()> > temp.key> => key> > temp.left, temp.right> => None> ,> None> > return> temp> # Function to find the height(depth) of the tree> def> height(root):> > # Initialising a variable to count the> > # height of tree> > depth> => 0> > q> => []> > # appending first level element along with None> > q.append(root)> > q.append(> None> )> > while> (> len> (q)>> 0> ):> > temp> => q[> 0> ]> > q> => q[> 1> :]> > # When None encountered, increment the value> > if> (temp> => => None> ):> > depth> +> => 1> > # If None not encountered, keep moving> > if> (temp !> => None> ):> > if> (temp.left):> > q.append(temp.left)> > if> (temp.right):> > q.append(temp.right)> > # If queue still have elements left,> > # append None again to the queue.> > elif> (> len> (q)>> 0> ):> > q.append(> None> )> > return> depth> # Driver program> # Let us create Binary Tree shown in above example> root> => newNode(> 1> )> root.left> => newNode(> 2> )> root.right> => newNode(> 3> )> root.left.left> => newNode(> 4> )> root.left.right> => newNode(> 5> )> print> (f> 'Height(Depth) of tree is: {height(root)}'> )> # This code is contributed by shinjanpatra>

C#

// C# Program to find the Maximum Depth or Height of Binary Tree> using> System;> using> System.Collections.Generic;> // A Tree node> public> class> Node {> > public> int> data;> > public> Node left, right;> > public> Node(> int> item)> > {> > data = item;> > left => null> ;> > right => null> ;> > }> }> public> class> BinaryTree {> > Node root;> > // Function to find the height(depth) of the tree> > int> height()> > {> > // Initialising a variable to count the> > // height of tree> > int> depth = 0;> > Queue q => new> Queue();> > // Pushing first level element along with NULL> > q.Enqueue(root);> > q.Enqueue(> null> );> > while> (q.Count != 0) {> > Node temp = q.Dequeue();> > // When NULL encountered, increment the value> > if> (temp ==> null> )> > depth++;> > // If NULL not encountered, keep moving> > if> (temp !=> null> ) {> > if> (temp.left !=> null> ) {> > q.Enqueue(temp.left);> > }> > if> (temp.right !=> null> ) {> > q.Enqueue(temp.right);> > }> > }> > // If queue still have elements left,> > // push NULL again to the queue> > else> if> (q.Count != 0) {> > q.Enqueue(> null> );> > }> > }> > return> depth;> > }> > // Driver program> > public> static> void> Main()> > {> > // Let us create Binary Tree shown in above example> > BinaryTree tree => new> BinaryTree();> > tree.root => new> Node(1);> > tree.root.left => new> Node(2);> > tree.root.right => new> Node(3);> > tree.root.left.left => new> Node(4);> > tree.root.left.right => new> Node(5);> > Console.WriteLine(> 'Height(Depth) of tree is: '> > + tree.height());> > }> }> // This code is contributed by Yash Agarwal(yashagarwal2852002)>

JavaScript

> // JavaScript code to implement the approach> // A Tree node> class Node{> > constructor(){> > this> .key = 0> > this> .left => null> > this> .right => null> > }> }> // Utility function to create a new node> function> newNode(key){> > let temp => new> Node()> > temp.key = key> > temp.left => null> > temp.right => null> > return> temp> }> // Function to find the height(depth) of the tree> function> height(root){> > // Initialising a variable to count the> > // height of tree> > let depth = 0> > let q = []> > > // pushing first level element along with null> > q.push(root)> > q.push(> null> )> > while> (q.length>0){> > let temp = q.shift()> > > // When null encountered, increment the value> > if> (temp ==> null> )> > depth += 1> > > // If null not encountered, keep moving> > if> (temp !=> null> ){> > if> (temp.left)> > q.push(temp.left)> > > if> (temp.right)> > q.push(temp.right)> > }> > > // If queue still have elements left,> > // push null again to the queue.> > else> if> (q.length>0)> > q.push(> null> )> > }> > return> depth> }> // Driver program> // Let us create Binary Tree shown in above example> let root = newNode(1)> root.left = newNode(2)> root.right = newNode(3)> root.left.left = newNode(4)> root.left.right = newNode(5)> document.write(`Height(Depth) of tree is: ${height(root)}`,> ''> )> // This code is contributed by shinjanpatra> >

Wyjście

Height(Depth) of tree is: 3 

Złożoność czasowa: NA)
Przestrzeń pomocnicza: NA)

Inna metoda znajdowania wysokości za pomocą Przechodzenie przez poziom zamówienia :

Ta metoda wykorzystuje również koncepcję przechodzenia przez kolejność poziomów, ale nie będziemy dodawać wartości null w kolejce. Po prostu zwiększ lada gdy poziom wzrośnie, wepchnij dzieci bieżącego węzła do kolejki, a następnie usuń wszystkie węzły z kolejki bieżącego poziomu.

C++

// C++ program for above approach> #include> using> namespace> std;> // A Tree node> struct> Node {> > int> key;> > struct> Node *left, *right;> };> // Utility function to create a new node> Node* newNode(> int> key)> {> > Node* temp => new> Node;> > temp->klucz = klucz;> > temp->lewy = temp->prawy = NULL;> > return> (temp);> }> /*Function to find the height(depth) of the tree*/> int> height(Node* root)> {> > // Initialising a variable to count the> > // height of tree> > queue q;> > q.push(root);> > int> height = 0;> > while> (!q.empty()) {> > int> size = q.size();> > for> (> int> i = 0; i Node* temp = q.front(); q.pop(); if (temp->lewy != NULL) { q.push(temp->lewy); } if (temp->right != NULL) { q.push(temp->right); } } wysokość++; } wysokość powrotu; } // Program sterownika int main() { // Stwórzmy drzewo binarne pokazane w powyższym przykładzie Node* root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->lewy->lewy = newNode(4); root->lewy->prawy = newNode(5); cout < < 'Height(Depth) of tree is: ' < < height(root); } // This code is contributed by Abhijeet Kumar(abhijeet19403)>

Jawa

// Java program for above approach> import> java.util.LinkedList;> import> java.util.Queue;> class> GFG {> > // A tree node structure> > static> class> Node {> > int> key;> > Node left;> > Node right;> > }> > // Utility function to create> > // a new node> > static> Node newNode(> int> key)> > {> > Node temp => new> Node();> > temp.key = key;> > temp.left = temp.right => null> ;> > return> temp;> > }> > /*Function to find the height(depth) of the tree*/> > public> static> int> height(Node root)> > {> > // Initialising a variable to count the> > // height of tree> > Queue q => new> LinkedList();> > q.add(root);> > int> height => 0> ;> > while> (!q.isEmpty()) {> > int> size = q.size();> > for> (> int> i => 0> ; i Node temp = q.poll(); if (temp.left != null) { q.add(temp.left); } if (temp.right != null) { q.add(temp.right); } } height++; } return height; } // Driver Code public static void main(String args[]) { Node root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); System.out.println('Height(Depth) of tree is: ' + height(root)); } }>

Python3

# Python3 program to find the height of a tree> > # A binary tree node> class> Node:> > > # Constructor to create a new node> > def> __init__(> self> , data):> > self> .key> => data> > self> .left> => None> > self> .right> => None> > # Function to find height of tree> def> height(root):> > # Base Case> > if> root> is> None> :> > return> 0> > > # Create an empty queue for level order traversal> > q> => []> > > # Enqueue Root and initialize height> > q.append(root)> > height> => 0> > > # Loop while queue is not empty> > while> q:> > > # nodeCount (queue size) indicates number of nodes> > # at current level> > nodeCount> => len> (q)> > > # Dequeue all nodes of current level and Enqueue all> > # nodes of next level> > while> nodeCount>> 0> :> > node> => q.pop(> 0> )> > if> node.left> is> not> None> :> > q.append(node.left)> > if> node.right> is> not> None> :> > q.append(node.right)> > nodeCount> -> => 1> > height> +> => 1> > > return> height> > # Driver Code> root> => Node(> 1> )> root.left> => Node(> 2> )> root.right> => Node(> 3> )> root.left.left> => Node(> 4> )> root.left.right> => Node(> 5> )> > print> (> 'Height(Depth) of tree is'> , height(root))>

C#

using> System;> using> System.Collections.Generic;> class> GFG {> > // A Tree node> > class> Node {> > public> int> key;> > public> Node left, right;> > public> Node(> int> key)> > {> > this> .key=key;> > this> .left=> this> .right=> null> ;> > }> > }> > // Utility function to create a new node> > /*Node newNode(int key)> > {> > Node* temp = new Node;> > temp.key = key;> > temp.left = temp.right = NULL;> > return (temp);> > }*/> > /*Function to find the height(depth) of the tree*/> > static> int> height(Node root)> > {> > // Initialising a variable to count the> > // height of tree> > Queue q=> new> Queue();> > q.Enqueue(root);> > int> height = 0;> > while> (q.Count>0) {> > int> size = q.Count;> > for> (> int> i = 0; i Node temp = q.Peek(); q.Dequeue(); if (temp.left != null) { q.Enqueue(temp.left); } if (temp.right != null) { q.Enqueue(temp.right); } } height++; } return height; } // Driver program public static void Main() { // Let us create Binary Tree shown in above example Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); Console.Write('Height(Depth) of tree is: ' + height(root)); } } // This code is contributed by poojaagarwal2.>

JavaScript

// JavaScript program for above approach> // a tree node> class Node{> > constructor(key){> > this> .key = key;> > this> .left => this> .right => null> ;> > }> }> // utility function to create a new node> function> newNode(key){> > return> new> Node(key);> }> // function to find the height of the tree> function> height(root){> > // initialising a variable to count the> > // height of tree> > let q = [];> > q.push(root);> > let height = 0;> > while> (q.length>0){> > let size = q.length;> > for> (let i = 0; i let temp = q.shift(); if(temp.left != null){ q.push(temp.left); } if(temp.right != null){ q.push(temp.right); } } height++; } return height; } // driver code let root = newNode(1); root.left = newNode(2); root.right = newNode(3); root.left.left = newNode(4); root.left.right = newNode(5); document.write('Height(Depth) of tree is: ' + height(root)); // this code is contributed by Kirti Agarwal(kirtiagarwal23121999)>

Wyjście

Height(Depth) of tree is: 3 

Złożoność czasowa: NA)
Przestrzeń pomocnicza: NA)