Cho mảng arr[] kích thước n biểu diễn cây (arr[i] là cha của i). Nhiệm vụ: tìm chiều cao cây nhị phân.
Cây nhị phân tìm kiếm (BST): Nút trái < cha, nút phải >= cha.
Chiều cao cây: Số nút trên đường từ gốc đến lá xa nhất.
Phương pháp giải
Cách đơn giản: xây dựng cây từ mảng cha, tìm gốc, đệ quy tính chiều cao.
Cách hiệu quả: Tính độ sâu từng nút từ mảng cha, lưu vào mảng depth. Trả về max depth.
Chương trình minh họa
Ví dụ
#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;
}
Kết quả
The maximum height of binary Tree is 3