實作概念:
建構關聯樹(每個節點紀錄下一層的關聯節點與父節點)。使用 DFS 進行節點走訪。
因為 DFS 的特性,在走訪過程,可以由葉節點,往回累計由葉節點回推的深度。
在每個節點 i 紀錄該節點向下延伸最長的兩段長度和 D(i) = top1Length(i)+top2Length(i)。
該題答案要找的答案,就是所有節點中最大的長度和 max( D(i) )
1. 本題一開始使用函式遞迴實作 DFS ,在測資4 ,因為呼叫太多層會引發 StackOverflowError 問題。
解法:使用 Stack 堆疊 + 迴圈實作 DFS,不用遞迴函示實作。
2. 測資 4 ,使用 Scanner 讀取資料會遇到 TLE 問題。
解法:在讀取資料改用 BufferedReader 會快很多。