二分木の最大深さ


難易度 簡単に
よく聞かれる Amazon (アマゾン) ケイデンスインド クーポンドゥニア ファクトセット 費用無料 MakeMyTrip モノタイプソリューション Snapdeal シノプシス Teradataの ヴイエムウェア Zohoの
深さ優先探索 ツリートラバーサル

問題文

「二分木の最大深さ」の問題は、二分木のデータ構造が与えられていることを示しています。 指定された最大深度を印刷します 二分木.

入力

二分木の最大深さ

2

説明:指定されたツリーの最大深度は2です。これは、左右のサブツリーの両方で、ルートの下に(つまり、ルートレベル= 1よりも深い)要素がXNUMXつしかないためです。

入力

二分木の最大深さ

3

説明:右側のサブツリーのレベル= 3に3つの要素があります。 したがって、最大深度= XNUMXです。

二分木の最大深度のアルゴリズム

1. Initialize a binary tree data structure.
2. Create a class node with a variable of integer type and the two-node type pointers left and right as it's private members.
3. Create a function newNode to create a new node of the binary tree which accepts a variable of integer type consisting of data as it's a parameter.
4. After that, initialize a new node inside it. Store the integer variable given as a parameter in the data of the node of the binary tree and update the value of it's left and the right pointer is null.
5. Return the newly created node.
6. Similarly, create a function to find the maximum depth of the binary tree which accepts a node pointer as it's a parameter.
7. Check if the node is equal to null, return 0.
8. Else create a variable left of integer type representing the depth of the left subtree. Make a recursive call to the function itself with the left of the node as it's a parameter and store the result returned in the variable left.
9. Similarly, create a variable right of integer type representing the depth of the right subtree. Make a recursive call to the function itself with the right of the node as it's a parameter and store the result returned in the variable right.
10. After that, check if the depth of the left subtree is greater than the depth of the right subtree return the depth of the left subtree + 1.
11. Else return the variable right i.e. the depth of the right subtree + 1.

二分木データ構造、左右のノードがあり、それ自体に左右のボードがあります。 したがって、ツリーのようなデータ構造を作成します。 二分木では、ノードを接続してサブツリーを作成します。 したがって、二分木データ構造のいくつかの用語を定義します。 そして、そのうちのXNUMXつは最大の深さです。これは、根から葉までの距離である木の最大の高さとして定義されます。 葉は、左ノードも右ノードも持たないノードに他なりません。

最大深度を見つけるために、左右のサブツリーの深度を計算します。 現在のツリーの深さは、左右のサブツリーの最大値+1に等しくなります。 したがって、再帰的アプローチを使用して、左右のサブツリーの深さを見つけます。 再帰を使用しているため、いくつかの基本ケースが必要です。 ここでの基本的なケースは、リーフであるノードにいる場合です。 リーフノードの長さは1です。

コード

二分木の最大の深さを見つけるためのC ++プログラム

#include <bits/stdc++.h> 
using namespace std; 
  
class node{  
    public: 
        int data;  
        node* left;  
        node* right;  
};  
  
int maxDepth(node* node){  
    if(node == NULL)  
        return 0;  
    else{  
        int left = maxDepth(node->left);  
        int right = maxDepth(node->right);  
      
        if(left > right)  
            return(left + 1);  
        else return(right + 1);  
    }  
}  
  
node* newNode(int data){  
    node* Node = new node(); 
    Node->data = data;  
    Node->left = NULL;  
    Node->right = NULL;  
      
    return(Node);  
}  
      
int main(){  
    node *root = newNode(2);  
  
    root->left = newNode(3);  
    root->right = newNode(8);  
    root->left->left = newNode(6);  
    root->left->right = newNode(9);  
      
    cout<<maxDepth(root);  
    return 0;  
}
3

二分木の最大の深さを見つけるJavaプログラム

class Node{ 
    int data; 
    Node left, right; 
   
    Node(int item){ 
        data = item; 
        left = right = null; 
    } 
} 
   
class BinaryTree{ 
     Node root; 
   
    int maxDepth(Node node){ 
        if(node == null) 
            return 0; 
        else{ 
            int left = maxDepth(node.left); 
            int right = maxDepth(node.right); 
   
            if(left > right) 
                return (left + 1); 
             else 
                return (right + 1); 
        } 
    } 
       
    public static void main(String[] args){ 
        BinaryTree tree = new BinaryTree(); 
   
        tree.root = new Node(2); 
        tree.root.left = new Node(3); 
        tree.root.right = new Node(8); 
        tree.root.left.left = new Node(6); 
        tree.root.left.right = new Node(9); 
   
        System.out.println(tree.maxDepth(tree.root)); 
    } 
}
3

複雑さの分析

時間の複雑さ

オン) ここで、nは、指定されたバイナリツリーに挿入されたデータノードの数です。

スペースの複雑さ

O(1) 一定の余分なスペースを使用したためです。

リファレンス