摘要：套路三：找到整個遞歸的終止條件。上述找返回值以及本級遞歸做什麼就是如下操作：。

很多故事都有個前言

一些常見的算法題都可以用遞歸解決，如果你看過很多leetcode上的題目你就知道了。熟練掌握了遞歸你也能像別人那樣直接幾行代碼很帥的解決了這個算法題。

常見教科書式的遞歸介紹

我們在大學裏甚至畢業後看的一些數據結構或者算法題裏都有遞歸的介紹，通常會用階乘介紹遞歸。如下

假設我們用遞歸來算階乘 f(n)

f = n =>
    n === 1 ? 1
            : n * f(n-1)

f 裏面用到了 f，怎麼理解呢？很簡單，把式子展開即可：

f(6)
=> 6 * f(5)
=> 6 * (5 * f(4))
=> 6 * (5 * (4 * f(3)))
=> 6 * (5 * (4 * (3 * f(2))))
=> 6 * (5 * (4 * (3 * (2 * f(1)))))
=> 6 * (5 * (4 * (3 * (2 * 1))))
=> 6 * (5 * (4 * (3 * 2)))
=> 6 * (5 * (4 * 6))
=> 6 * (5 * 24)
=> 6 * 120
=> 720


先遞進，再回歸——這就是「遞歸」。到這裏是不是對這個概念很熟悉了。

那麼遞歸到底能解決那些算法題呢？

  • Leetcode 104. 二叉樹的最大深度

  • Leetcode 24. 兩兩交換鏈表中的節點

  • Leetcode 110. 平衡二叉樹

  • ......等等

遞歸的套路

套路一：不要糾結遞歸的整個過程。

既然遞歸是一個反覆調用自身的過程，這就說明它每一級的功能都是一樣的，因此我們只需要關注一級遞歸的解決過程即可。

套路二：這個主函數是做什麼的。

套路三：找到整個遞歸的終止條件。

套路四：找返回值：應該給上一級返回什麼信息。

套路五：我們精簡後的一級遞歸是用來做什麼的。

既然找到攻略了我們下面實踐下

給定一個二叉樹，找出其最大深度。

二叉樹的深度爲根節點到最遠葉子節點的最長路徑上的節點數。

說明: 葉子節點是指沒有子節點的節點。

示例：給定二叉樹 [3,9,20,null,null,15,7]

3

/ \

9 20

/ \

15 7

返回它的最大深度 3 。

  • 按照上面的套路我們先構造主函數

- (NSInteger)maxDepthOfTree:(DSTreeNode *)root

  • 找整個遞歸的終止條件：遞歸應該在什麼時候結束？樹爲空的時候，此時樹的深度爲0，遞歸就結束了。

    if (root == nil)
        {
            return 0;
        }

  • 找返回值：應該給上一級返回什麼？當前節點的最大深度

  • 本級遞歸應該做什麼：在這一級遞歸中，要做什麼？

上述找返回值以及本級遞歸做什麼就是如下操作：

maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1

那麼綜合下這題的解題過程如下：

- (NSInteger)maxDepthOfTree:(DSTreeNode *)root
{
//1
    if (root == nil)
    {
        return 0;
    }
    //2
    else
    {
        NSInteger left_height = [self maxDepthOfTree:root.leftChild];
        NSInteger right_height = [self maxDepthOfTree:root.rightChild];
        return MAX(left_height, right_height)+1;

    }
}

看到這裏是不是發現原來如此，按照這個套路向裏面套代碼就行了。

總結

數據結構的基本存儲方式就是鏈式和順序兩種，基本操作就是增刪查改，遍歷方式無非迭代和遞歸。所以掌握遞歸還是比較重要的。

如果感覺這篇文章不錯可以點擊在看:point_down:

相關文章