C++에서 부모 배열로 표현되는 이진 트리의 높이 찾기

이 문제에서는 트리를 나타내는 n 크기의 배열 arr[]이 제공됩니다. 우리의 임무는 Parent 배열이 나타내는 Binary Tree의 높이를 찾는 것입니다.

이진 검색 트리(BST) 모든 노드가 아래에 언급된 속성을 따르는 트리입니다 -

• 왼쪽 하위 트리의 키 값이 상위(루트) 노드의 키 값보다 작습니다.
• 오른쪽 하위 트리의 키 값이 상위(루트) 노드의 키 값보다 크거나 같습니다.

나무 높이 루트 노드에서 가장 먼 잎 노드로 이동할 때 통과하는 노드의 수입니다.

해결 방법:

문제에 대한 간단한 해결책은 부모 배열에서 트리를 만드는 것입니다. 이 트리의 루트를 찾고 찾은 인덱스에 대해 반복하여 왼쪽 및 오른쪽 하위 트리를 만든 다음 최대 높이를 반환합니다.

더 효율적인 방법은 배열에서 노드의 깊이를 계산하고 깊이 배열에 저장한 다음 저장하는 것입니다. 이 배열에서 최대 깊이를 반환합니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#include <bits/stdc++.h>
using namespace std;

void findAllDepths(int arr[], int i, int nodeDepth[]) {
   
   if (nodeDepth[i])
      return;
   if (arr[i] == -1) {
     
      nodeDepth[i] = 1;
      return;
   }
   if (nodeDepth[arr[i]] == 0)
      findAllDepths(arr, arr[i], nodeDepth);
   nodeDepth[i] = nodeDepth[arr[i]] + 1;
}

int findMaxHeightBT(int arr[], int n) {

   int nodeDepth[n];
   for (int i = 0; i < n; i++)
      nodeDepth[i] = 0;
   for (int i = 0; i < n; i++)
      findAllDepths(arr, i, nodeDepth);
   int maxHeight = nodeDepth[0];
   for (int i=1; i<n; i++)
      if (maxHeight < nodeDepth[i])
         maxHeight = nodeDepth[i];
   return maxHeight;
}

int main() {
   
   int arr[] = {-1, 0, 0, 1, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum height of binary Tree is "<<findMaxHeightBT(arr, n);
   return 0;
}

출력 -

The maximum height of binary Tree is 3