資料結構
網路
關係資料庫管理系統 (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 次檢視
廣告