用 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

sudhir sharma

更新于：2021年1月22日

160 次查看

开启你的职业生涯

完成课程获得认证

开始学习