Երկուական ծառի առավելագույն խորությունը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Կադենս Հնդկաստան CouponDunia Փաստեր Անվճար լիցքավորում MakeMyTrip- ը Մոնոտիպ լուծումներ Snapdeal Սինոփսիս Տերադատա VMware Zoho
Խորությունը առաջին որոնում ծառ Reeառի անցում

Խնդիրի հայտարարություն

«Երկուական ծառի առավելագույն խորություն» խնդրում նշվում է, որ ձեզ տրվում է տվյալների երկուական ծառի կառուցվածք: Տպիր տրվածի առավելագույն խորությունը երկուական ծառ.

Օրինակ

Մուտքային

Երկուական ծառի առավելագույն խորությունը

2

Բացատրություն. Տրված ծառի համար առավելագույն խորությունը 2-ն է. Քանի որ արմատից ներքև կա միայն մեկ տարր (այսինքն `արմատից ավելի մեծ խորության վրա = 1) և՛ ձախ, և՛ աջ ենթածառում:

Մուտքային

Երկուական ծառի առավելագույն խորությունը

3

Բացատրություն. Աջ ենթափայտում = 3 մակարդակի վրա կա երկու տարր: Այսպիսով առավելագույն խորությունը = 3:

Երկուական ծառի առավելագույն խորության ալգորիթմ

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.

Է երկուական ծառի տվյալների կառուցվածք, մենք ունենք ձախ և աջ հանգույցներ, որոնք այնուհետև ունեն ձախ և աջ հանգույցներ: Այսպիսով, կազմելով ծառի նման տվյալների կառուցվածք: Երկուական ծառի մեջ հանգույցները միացված են ՝ ենթատառեր ստեղծելու համար: Այսպիսով, մենք սահմանում ենք որոշ տերմինաբանություն երկուական ծառի տվյալների կառուցվածքի համար: Եվ դրանցից մեկը առավելագույն խորությունն է, որը սահմանվում է որպես ծառի առավելագույն բարձրություն ՝ արմատից տերև հեռավորությունը: Տերեւը ոչ այլ ինչ է, քան մի հանգույց, որը չունի թե ձախ, թե աջ հանգույց:

Առավելագույն խորությունը գտնելու համար մենք հաշվարկում ենք ձախ և աջ ենթատեսակի խորությունը: Ընթացիկ ծառի խորությունը հավասար է ձախ և աջ ենթատեսակի +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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ) որտեղ n- ը տրված երկուական ծառի մեջ տեղադրված տվյալների հանգույցների թիվն է:

Տիեզերական բարդություն

Ո (1) քանի որ մենք օգտագործում էինք անընդհատ լրացուցիչ տարածք:

Սայլակ