Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n biểu thị một cây. Nhiệm vụ của chúng ta là tìm chiều cao của Binary Tree được biểu diễn bởi mảng Parent.
A Cây tìm kiếm nhị phân (BST) là một cây trong đó tất cả các nút tuân theo các thuộc tính được đề cập bên dưới -
- Giá trị của khóa của cây con bên trái nhỏ hơn giá trị của khóa của nút cha (gốc).
- Giá trị của khóa của cây con bên phải lớn hơn hoặc bằng giá trị của khóa của nút cha (gốc) của nó.
Chiều cao của cây là số nút được duyệt khi đi từ nút gốc đến nút lá xa nhất.
Phương pháp tiếp cận giải pháp:
Một giải pháp đơn giản cho vấn đề là tạo một cây từ mảng mẹ. Tìm gốc của cây này và lặp lại cho chỉ mục tìm thấy tạo cây con bên trái và bên phải, sau đó trả về chiều cao tối đa.
Một phương pháp hiệu quả hơn sẽ là tính toán độ sâu của các nút từ mảng và lưu trữ sau đó lưu trữ nó trong mảng độ sâu. Từ mảng này trả về độ sâu tối đa.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
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;
} Đầu ra -
The maximum height of binary Tree is 3