หาความสูงของ Binary Tree ที่แทนด้วย Parent Array ใน C++

โจทย์

ได้รับอาร์เรย์ arr[] ขนาด n ที่แทนต้นไม้ (Parent Array) โดย arr[i] = parent ของโหนด i (รูทมีค่า -1) ทางเราต้อง หาความสูงของ Binary Tree

แนวทางแก้ปัญหา

วิธีที่มีประสิทธิภาพ (O(n)): คำนวณความลึก (Depth) ของแต่ละโหนดด้วย Memoization (DP)

1. สร้างอาร์เรย์ nodeDepth[] เริ่มต้น 0
2. ฟังก์ชัน findAllDepths(i):
   • ถ้าคำนวณแล้ว -> คืนค่า
   • ถ้าเป็นรูท (arr[i] == -1) -> depth = 1
   • หา depth ของ parent ก่อน แล้ว depth[i] = depth[parent] + 1
3. หาค่า max ใน nodeDepth[]

โปรแกรมตัวอย่าง

#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