数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学用 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
更新于：2021年1月22日
160 次查看
广告