C++で親配列によって表される二分木の高さを見つける

この問題では、ツリーを表すサイズnの配列arr[]が与えられます。私たちのタスクは、親配列で表される二分木の高さを見つけることです。

二分探索木（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