BG79 面試刷題：分裂二叉樹的最大乘積

【原創】From 青衣極客 Blue Geek In 2020-04-03

“遞歸”是一個會讓每個初學計算機編程的人都頭暈的概念，但是它簡單的形式又讓我們在描述和解決問題時有了極大的便利。

1. 題目 Q1339 分裂二叉樹的最大乘積

給定二叉樹的 root。通過刪除一個邊，將二叉樹分成兩個子樹，以使子樹之和的乘積最大化。由於答案可能太大，請以10 ^ 9 + 7為模返回。

約束條件：

<code>(a) 每棵樹的節點數量在[2,50000]範圍內
(b) 每棵樹存儲的值在[1,10000]範圍內/<code>

示例1

<code>Input: root = [1,2,3,4,5,6]
Output: 110/<code>

解釋： 移除“1”和“2”之間的邊，所得的兩個子樹的和分別為11、10，它們的乘積是110。

示例2

<code>Input: root = [1,null,2,3,4,null,null,5,6]
Output: 90/<code>

解釋： 移除“2”與“4”之間的邊，所得兩個子樹的和分別為6、15，他們的乘積是90.

示例3

<code>Input: root = [2,3,9,10,7,8,6,5,4,11,1]
Output: 1025/<code>

示例4

<code>Input: root = [1,1]
Output: 1/<code>

2. 求解思路

很快有了一個最直觀的思路：在移除一條邊時，分別計算新形成的兩棵樹中元素之和，然後記錄乘積；遍歷所有的邊，嘗試移除操作，最後選擇出最大的乘積即可。

這個思路是否有可以優化的點呢？至少有一點，可以先將每個節點上所記錄的數組修改為其所在子樹上所有節點的和，這樣一次遍歷即可完成，而不需每次都重複計算。這個預處理操作使用“遞歸”來實現也是非常簡單的。每個節點的值應當是其本身存儲的值以及其左右子樹各自和的疊加，這一描述構成了邏輯上的重複和遞推。以下代碼可以準確描述這種邏輯：

接著需要進行操作就是嘗試移除每一個邊，然後保存乘積最大的值即可，這一步也可以使用遞歸完成。

3. 解決方案

這裡提供一種使用遞歸求解的C++解決方案。

從這個解決方案來看，兩個子函數分別完成“子樹求和”與“枚舉所有邊”這兩個功能。從代碼中可以看出，雖然這兩個子函數完成的功能不同，但是其邏輯結構是非常相似的。都是先確定“遞歸”結束條件，然後分別對左子樹和右子樹進行同樣的邏輯操作。這也說明了“遞歸”的兩大重點：(1)設置結束條件，(2)針對子結構重複調用。如果沒有正確設置重點(1)，可能會出現無窮遞歸，從而導致堆棧溢出的錯誤；如果沒有正確編寫重點(2)，則會造成最終結果可能不正確。

當提到“重複調用”時，我們很容易聯想到“循環”，事實上“循環”的作用就是為了簡化重複邏輯的，那麼“循環”與“遞歸”有什麼區別呢？簡單來說，“循環”是指時間上的重複，“遞歸”是指結構上的重複。事實上，所有的“遞歸邏輯”都可以使用“循環”來實現。而且由於避免了頻繁的壓入和彈出堆棧，還能有不少執行效率上的提升。但其缺點也很明顯，即邏輯的實現形式非常複雜，有時還具有很強的技巧，不是那麼容易實現的。

閱讀更多 青衣極客 的文章

關鍵字: 算法 人生第一份工作 二叉樹