解題思路:
題目要求找出兩個血緣關係最遠的成員之距離。
首先可以發現,距離的其中一端必定包含位於最深處的節點(才能讓關係最遙遠),
接著只需要找出位於另一端的節點,即可求得最遠的血緣距離。
實作策略:
為了找出位於最深處的節點之一,我們需要先知道誰是根節點。而根節點只要能夠成功建立樹結構,就能輕易得出。
其次需要找到位於最深處的節點。我們可以利用 BFS ,從根節點開始逐層搜尋,並維護最深的節點。
其實這部分用 DFS 也可以找到,只是在實作上,會多了需要判斷當前節點高度的步驟,不像 BFS 會自然維護節點距離,
較為繁瑣且容易出錯,故推薦使用 BFS 實作。
在取得最深處的節點後,以其作為起點,進行第二次 BFS ,並計算各節點與其的距離,在找到最遠處節點後即可完成。