前往
大廳
主題

LeetCode - 543. Diameter of Binary Tree 解題心得

Not In My Back Yard | 2020-11-14 00:00:04 | 巴幣 2 | 人氣 406

題目連結:


題目意譯:
給定一棵二元樹,你需要計算這棵樹的直徑長。二元樹的直徑定義為樹的任意兩節點中最長的路徑之長度。這個路徑可能會也可能不會通過根節點。

注:兩個節點的路徑之長度以兩者之間的邊數所代表。



範例測資:
給定二元樹
    1
   / \
  2   3
 / \
4  5
回傳 3 ,其為 [4,2,1,3] 或 [5,2,1,3] 的路徑長度。   



解題思維:
樹直徑很特別,當你在求整棵樹的最大深度時(如這題),你可以順便求得樹直徑之值。

定義 D 為儲存樹直徑之值的變數。並假設用上面題目作法下的目前遞迴而得的左子樹最大深度為 L 、右子樹最大深度為 R ,可以看到本層遞迴要回傳的深度值應為 max(L, R) + 1 (L 、 R 兩者哪個大,誰就 + 1)。

而我們可以更新 D 值為 max(D, L + R)。當整個求深度的遞迴結束(即求得深度值)時,此時的 D 即是最終所求。



為什麼這樣可行呢?因為可以看到為樹直徑的那條路徑會經過某些子樹的根節點。假設我們在盡量靠近整個樹的那棵子樹的根節點上,可以看到該路徑的長度即為左子樹最遠的葉節點經過此子樹的根節點到右子樹最遠的葉節點。而最遠的葉節點到根節點的距離即是最大深度之定義。

因此我們只需要對於每棵子樹,判斷哪個子樹求出來的左子樹最大深度 + 右子樹最大深度之值(這邊不 + 1 是因為本題的長度定義為路徑上的邊數)最大即是樹直徑。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作