ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ขนาด n ที่ระบุถึงต้นไม้ งานของเราคือ ค้นหาความสูงของต้นไม้ไบนารีที่แสดงโดยอาร์เรย์หลัก
โครงสร้างการค้นหาแบบไบนารี (BST) เป็นต้นไม้ที่โหนดทั้งหมดเป็นไปตามคุณสมบัติที่กล่าวถึงด้านล่าง -
- ค่าของคีย์ของแผนผังย่อยด้านซ้ายจะน้อยกว่าค่าของคีย์ของโหนดหลัก (root)
- ค่าของคีย์ของแผนผังย่อยที่ถูกต้องมากกว่าหรือเท่ากับค่าของคีย์ของโหนดหลัก (root)
ความสูงของต้นไม้ คือจำนวนโหนดที่ข้ามผ่านเมื่อเปลี่ยนจากโหนดรากไปยังโหนดปลายสุดที่ไกลที่สุด
แนวทางแก้ไข:
วิธีแก้ปัญหาอย่างง่ายคือการสร้างทรีจากอาร์เรย์หลัก การค้นหารูทของทรีนี้และเกิดซ้ำสำหรับดัชนีที่พบโดยสร้างทรีย่อยด้านซ้ายและขวา จากนั้นคืนค่าความสูงสูงสุด
วิธีที่มีประสิทธิภาพมากขึ้นคือการคำนวณความลึกของโหนดจากอาร์เรย์และจัดเก็บในอาร์เรย์ความลึก จากอาร์เรย์นี้จะคืนค่าความลึกสูงสุด
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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
