10503第4題血緣關係

解題策略(二)

使用深度優先搜尋(DFS)走訪樹狀結構，演算法步驟如下。

Step1)找出根(root)節點，由根(root) 節點出發進行深度優先搜尋(DFS)，也就是定義深度優先搜尋(DFS)函式，使用根(root) 節點為輸入，可以寫成DFS(root)。

Step2)深度優先搜尋(DFS)函式的程式結構，如下。

若該點沒有小孩，則回傳0，遞迴中止。

若該點只有一個小孩，則回傳並遞迴呼叫「 DFS(該小孩)+1」。

若該點有兩個以上的小孩，則計算所有小孩最大深度的前兩名相加，計算相加最大值到廣域變數md。最後回傳最大深度值，為了只有一個小孩的「DFS(該小孩)」。

Step3)遞迴呼叫DFS(root)回傳結果到變數rd，取md與rd較大值就是答案。

C++參考程式碼