#30161: 較快的作法 葉節點到根節點


wer12369qaz15963@gmail.com (dentr)

School : 新北市立清水高中
ID : 174903
IP address : [111.248.152.60]
Last Login :
2022-07-26 15:13:49
c463. apcs 樹狀圖分析 (Tree Analyses) -- apcs | From: [219.84.98.239] | Post Date : 2022-05-02 14:48

相比 DFS 每個節點取深度 這題用這個方法更快

葉節點越多越慢

如果你是寫 python 或 Java  或者你想要這題更快的話 可以用這個做法

在測資時 把沒有子節點的節點紀錄下來 因為我們要從葉節點開始往上讀

以每個葉節點往上讀過各一遍 取H的最大值

例:

                7

            /

         2

      /     \

 3             4

                    \ 

                       5

以這個圖來說 當我從3開始走時 2的高度是1 當我以5開始走時 2的高度是2 要取最大值 所以 2的高度是2

所有葉節點的終點即為根節點 第一部分解決

把 所有高度總和 第二部份解決 

注意: 這題要迴圈 用遞迴 會因為呼叫太多次而錯誤

 

 
ZeroJudge Forum