[轉載]《程式設計之美: 求二叉樹中節點的最大距離》的另一個解法

本文提出的解法比原書清晰的多，全文轉載一下。

如果我們把二叉樹看成一個圖，父子節點之間的連線看成是雙向的，我們姑且定義"距離"為兩節點之間邊的個數。寫一個程式求一棵二叉樹中相距最遠的兩個節點之間的距離。

書中對這個問題的分析是很清楚的，我嘗試用自己的方式簡短覆述。

計算一個二叉樹的最大距離有兩個情況:

情況A: 路徑經過左子樹的最深節點，通過根節點，再到右子樹的最深節點。

情況B: 路徑不穿過根節點，而是左子樹或右子樹的最大距離路徑，取其大者。

隻需要計算這兩個情況的路徑距離，并取其大者，就是該二叉樹的最大距離。

我也想不到更好的分析方法。

這段代碼有幾個缺點:

算法加入了侵入式(intrusive)的資料nMaxLeft, nMaxRight

使用了全局變量 nMaxLen。每次使用要額外初始化。而且就算是不同的獨立資料，也不能在多個線程使用這個函數

邏輯比較複雜，也有許多 NULL 相關的條件測試。

我認為這個問題的核心是，情況A 及 B 需要不同的資訊: A 需要子樹的最大深度，B 需要子樹的最大距離。隻要函數能在一個節點同時計算及傳回這兩個資訊，代碼就可以很簡單:

計算 result 的代碼很清楚；nMaxDepth 就是左子樹和右子樹的深度加1；nMaxDistance 則取 A 和 B 情況的最大值。

為了減少 NULL 的條件測試，進入函數時，如果節點為 NULL，會傳回一個 empty 變量。比較奇怪的是 empty.nMaxDepth = -1，目的是讓調用方 +1 後，把目前的不存在的 (NULL) 子樹當成最大深度為 0。

除了提高了可讀性，這個解法的另一個優點是減少了 O(節點數目) 大小的侵入式資料，而改為使用 O(樹的最大深度) 大小的棧空間。這個設計使函數完全沒有副作用(side effect)。

以下也提供測試代碼給讀者參考 (頁數是根據第7次印刷，節點是由上至下、左至右編号):

你想到更好的解法嗎?

本文轉自五嶽部落格園部落格，原文連結：http://www.cnblogs.com/wuyuegb2312/articles/3174476.html，如需轉載請自行聯系原作者