遞歸的實戰演練(進階) | 算法必看系列六

原文連結

遞歸的實戰演練(進階)

初級題

接下來我們來看下一道經典的題目: 反轉二叉樹 将左邊的二叉樹反轉成右邊的二叉樹。

接下來讓我們看看用我們之前總結的遞歸解法四步曲如何解題。

1.定義一個函數，這個函數代表了翻轉以 root 為根節點的二叉樹

publicstaticclass TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public TreeNode invertTree(TreeNode root) {
}
           

2.查找問題與子問題的關系,得出遞推公式 我們之前說了，解題要采用自上而下的思考方式，那我們取前面的1， 2，3 結點來看，對于根節點 1 來說，假設 2, 3 結點下的節點都已經翻轉，那麼隻要翻轉 2， 3 節點即滿足需求

對于2， 3 結點來說，也是翻轉其左右節點即可,依此類推,對每一個根節點，依次翻轉其左右節點，是以我們可知問題與子問題的關系是 翻轉(根節點) = 翻轉(根節點的左節點) + 翻轉(根節點的右節點) 即

invert(root) = invert(root->left) + invert(root->right)           

而顯然遞歸的終止條件是當結點為葉子結點時終止（因為葉子節點沒有左右結點）

3.将第二步的遞推公式用代碼表示出來補充到步驟 1 定義的函數中

public TreeNode invertTree(TreeNode root) {
    // 葉子結果不能翻轉
    if (root == null) {
        returnnull;
    }
    // 翻轉左節點下的左右節點
    TreeNode left = invertTree(root.left);
    // 翻轉右節點下的左右節點
    TreeNode right = invertTree(root.right);

    // 左右節點下的二叉樹翻轉好後，翻轉根節點的左右節點
    root.right = left;
    root.left = right;
    return root;
}           

4.時間複雜度分析 由于我們會對每一個節點都去做翻轉，是以時間複雜度是 O(n)，那麼空間複雜度呢，這道題的空間複雜度非常有意思，我們一起來看下，由于每次調用 invertTree 函數都相當于一次壓棧操作， 那最多壓了幾次棧呢， 仔細看上面函數的下一段代碼

TreeNode left = invertTree(root.left);           

從根節點出發不斷對左結果調用翻轉函數, 直到葉子節點，每調用一次都會壓棧，左節點調用完後，出棧，再對右節點壓棧....,下圖可知棧的大小為3， 即樹的高度，如果是完全二叉樹 ，則樹的高度為logn, 即空間複雜度為O(logn)

最壞情況，如果此二叉樹是如圖所示(隻有左節點，沒有右節點)，則樹的高度即結點的個數 n，此時空間複雜度為 O(n),總的來看，空間複雜度為O(n)

說句題外話，這道題當初曾引起轟動，因為 Mac 下著名包管理工具 homebrew 的作者 Max Howell 當初解不開這道題，結果被 Google 拒了，也就是說如果你解出了這道題，就超越了這位世界大神，想想是不是很激動。

中級題

接下來我們看一下大學時學過的漢諾塔問題：　　如下圖所示，從左到右有A、B、C三根柱子，其中A柱子上面有從小疊到大的n個圓盤，現要求将A柱子上的圓盤移到C柱子上去，期間隻有一個原則：一次隻能移到一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數

接下來套用我們的遞歸四步法看下這題怎麼解

1.定義問題的遞歸函數，明确函數的功能,我們定義這個函數的功能為：把 A 上面的 n 個圓盤經由 B 移到 C

// 将 n 個圓盤從 a 經由 b 移動到 c 上
public void hanoid(int n, char a, char b, char c) {
}           

2.查找問題與子問題的關系 首先我們看如果 A 柱子上隻有兩塊圓盤該怎麼移

前面我們多次提到，分析問題與子問題的關系要采用自上而下的分析方式，要将 n 個圓盤經由 B 移到 C 柱上去，可以按以下三步來分析：

将上面的 n-1 個圓盤看成是一個圓盤,這樣分析思路就與上面提到的隻有兩塊圓盤的思路一緻了；

将上面的 n-1 個圓盤經由 C 移到 B ，此時将 A 底下的那塊最大的圓盤移到 C ；

再将 B 上的 n-1 個圓盤經由A移到 C上

有人問第一步的 n - 1 怎麼從 C 移到 B,重複上面的過程,隻要把 上面的 n-2個盤子經由 A 移到 B, 再把A最下面的盤子移到 C,最後再把上面的 n - 2 的盤子經由A 移到 B 下..., 怎麼樣，是不是找到規律了，不過在找問題的過程中 切忌把子問題層層展開,到漢諾塔這個問題上切忌再分析 n-3,n-4 怎麼移，這樣會把你繞暈，隻要找到一層問題與子問題的關系得出可以用遞歸表示即可。

由以上分析可得

move(n from A to C) = move(n-1 from A to B) + move(A to C) + move(n-1 from B to C`)           

一定要先得出遞歸公式，哪怕是僞代碼也好!這樣第三步推導函數編寫就容易很多，終止條件我們很容易看出，當 A 上面的圓盤沒有了就不移了

3.根據以上的遞歸僞代碼補充函數的功能

// 将 n 個圓盤從 a 經由 b 移動到 c 上
public void hanoid(int n, char a, char b, char c) {
    if (n <= 0) {
        return;
    }
    // 将上面的  n-1 個圓盤經由 C 移到 B
    hanoid(n-1, a, c, b);
    // 此時将 A 底下的那塊最大的圓盤移到 C
    move(a, c);
    // 再将 B 上的 n-1 個圓盤經由A移到 C上
    hanoid(n-1, b, a, c);
}

public void move(char a, char b) {
    printf("%c->%c\n", a, b);
}           

從函數的功能上看其實比較容易了解，整個函數定義的功能就是把 A 上的 n 個圓盤 經由 B 移到 C，由于定義好了這個函數的功能，那麼接下來的把 n-1 個圓盤 經由 C 移到 B 就可以很自然的調用這個函數,是以明确函數的功能非常重要,按着函數的功能來解釋，遞歸問題其實很好解析，切忌在每一個子問題上層層展開死摳,這樣這就陷入了遞歸的陷阱，計算機都會棧溢出，何況人腦

4.時間複雜度分析 從第三步補充好的函數中我們可以推斷出

f(n) = f(n-1) + 1 + f(n-1) = 2f(n-1) + 1 = 2(2f(n-2) + 1) + 1 = 2 * 2 * f(n-2) + 2 + 1 = 22 * f(n-3) + 2 + 1 = 22 * f(n-3) + 2 + 1 =  22 * (2f(n-4) + 1) = 23 * f(n-4) + 22  + 1 = ....        // 不斷地展開 = 2n-1 + 2n-2 + ....+ 1           

顯然時間複雜度為 O(2^n)，很明顯指數級别的時間複雜度是不能接受的，漢諾塔非遞歸的解法比較複雜，大家可以去網上搜一下

進階題

現實中大廠中的很多遞歸題都不會用上面這些相對比較容易了解的題，更加地是對遞歸問題進行相應地變形， 來看下面這道題

細胞分裂 有一個細胞 每一個小時分裂一次，一次分裂一個子細胞，第三個小時後會死亡。那麼n個小時候有多少細胞？

照樣我們用前面的遞歸四步曲來解

1.定義問題的遞歸函數，明确函數的功能 我們定義以下函數為 n 個小時後的細胞數

public int allCells(int n) {
}           

2.接下來尋找問題與子問題間的關系（即遞推公式） 首先我們看一下一個細胞出生到死亡後經曆的所有細胞分裂過程

圖中的 A 代表細胞的初始态, B代表幼年态(細胞分裂一次), C 代表成熟态(細胞分裂兩次)，C 再經曆一小時後細胞死亡 以 f(n) 代表第 n 小時的細胞分解數 fa(n) 代表第 n 小時處于初始态的細胞數, fb(n) 代表第 n 小時處于幼年态的細胞數 fc(n) 代表第 n 小時處于成熟态的細胞數 則顯然 f(n) = fa(n) + fb(n) + fc(n) 那麼 fa(n) 等于多少呢，以n = 4 （即一個細胞經曆完整的生命周期）為例

仔細看上面的圖

可以看出 fa(n) = fa(n-1) + fb(n-1) + fc(n-1), 當 n = 1 時，顯然 fa(1) = 1

fb(n) 呢,看下圖可知 fb(n) = fa(n-1)。當 n = 1 時 fb(n) = 0

fc(n) 呢,看下圖可知 fc(n) = fb(n-1)。當 n = 1,2 時 fc(n) = 0

綜上， 我們得出的遞歸公式如下

3.根據以上遞歸公式我們補充一下函數的功能

public int allCells(int n) {
    return aCell(n) + bCell(n) + cCell(n);
}

/**
 * 第 n 小時 a 狀态的細胞數
 */
public int aCell(int n) {
    if(n==1){
        return1;
    }else{
        return aCell(n-1)+bCell(n-1)+cCell(n-1);
    }
}

/**
 * 第 n 小時 b 狀态的細胞數
 */
public int bCell(int n) {
    if(n==1){
        return0;
    }else{
        return aCell(n-1);
    }
}

/**
 * 第 n 小時 c 狀态的細胞數
 */
public int cCell(int n) {
    if(n==1 || n==2){
        return0;
    }else{
        return bCell(n-1);
    }
}           

隻要思路對了，将遞推公式轉成代碼就簡單多了，另一方面也告訴我們，可能一時的遞歸關系我們看不出來，此時可以借助于畫圖來觀察規律

4.求時間複雜度 由第二步的遞推公式我們知道 f(n) = 2aCell(n-1) + 2aCell(n-2) + aCell(n-3)

之前青蛙跳台階時間複雜度是指數級别的，而這個方程式顯然比之前的遞推公式(f(n) = f(n-1) + f(n-2)) 更複雜的，是以顯然也是指數級别的

總結

大部分遞歸題其實還是有迹可尋的， 按照之前總結的解遞歸的四個步驟可以比較順利的解開遞歸題，一些比較複雜的遞歸題我們需要勤動手，畫畫圖，觀察規律，這樣能幫助我們快速發現規律，得出遞歸公式，一旦知道了遞歸公式，将其轉成遞歸代碼就容易多了,很多大廠的遞歸考題并不能簡單地看出遞歸規律，往往會在遞歸的基礎上多加一些變形，不過萬遍不離其宗，我們多采用自頂向下的分析思維，多練習，相信遞歸不是什麼難事。

來源 | 五分鐘學算法

作者 | 碼海