이진 트리의 최대 깊이

난이도 쉽게
자주 묻는 질문 아마존 케이던스 인도 쿠폰 Dunia 팩트 셋 무료 MakeMyTrip 모노 타입 솔루션 스냅 딜 Synopsys 테라 데이타 VM웨어 조호 (Zoho)
깊이 우선 검색 나무 트리 순회조회수 68

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

"최대 이진 트리 깊이"문제는 이진 트리 데이터 구조가 제공되었음을 나타냅니다. 주어진 최대 깊이를 인쇄하십시오 이진 트리.

입력

이진 트리의 최대 깊이

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

복잡성 분석

시간 복잡성

의 위에) 여기서 n은 주어진 이진 트리에 삽입 된 데이터 노드의 수입니다.

공간 복잡성

O (1) 일정한 추가 공간을 사용했기 때문입니다.

참조

균열 시스템 설계 인터뷰
Translate »