f673 - FJCU_109_Winter_Day2_Lab1 樹高

🔗 前往 ZeroJudge 原題

題目描述

題目給定一棵二元樹，要求計算這棵樹的高度。樹的表示方式為：給定 N 個節點，以及每個節點的左右子節點。節點編號從 0 到 N-1。高度定義為從根節點到最遠葉節點的路徑長度。

解題思路

這題可以使用深度優先搜尋 (DFS) 來計算樹的高度。從根節點 (節點 0) 開始，遞迴地遍歷左子樹和右子樹，並記錄當前路徑的深度。在遍歷過程中，更新最大深度，最終的最大深度即為樹的高度。

程式碼中，t[no][0] 和 t[no][1] 分別儲存節點 no 的左子節點和右子節點。dfs 函數遞迴地計算樹的高度。ans 變數用於儲存最大深度。

複雜度分析

• 時間複雜度: O(N)
• 空間複雜度: O(N)

程式碼

#include <iostream>
using namespace std;
int t[101][2],n,a,b,c,ans;
void dfs(int no,int step){
	if(no==-1)return;
	ans=max(step,ans);
	dfs(t[no][0],step+1);
	dfs(t[no][1],step+1);
}
int main(){
	cin >> n;
	for(int i=0;i<n;++i){
		cin >> a >> b >> c;
		t[a][0]=b;
		t[a][1]=c;
	}
	dfs(0,0);
	cout << ans;
}