轉自3道題徹底搞定：套路解決遞歸問題

前言

相信不少同學和我一樣，在剛學完數據結構后開始刷算法題時，遇到遞歸的問題總是很頭疼，而一看解答，卻發現大佬們幾行遞歸代碼就優雅的解決了問題。從我自己的學習經歷來看，剛開始理解遞歸思路都很困難，更別說自己寫了。

我一直覺得刷算法題和應試一樣，既然是應試就一定有套路存在。在刷題中，我總結出了一套解決遞歸問題的模版思路與解法，用這個思路可以秒解很多遞歸問題。

遞歸解題三部曲

何為遞歸？程序反復調用自身即是遞歸。

我自己在剛開始解決遞歸問題的時候，總是會去糾結這一層函數做了什么，它調用自身后的下一層函數又做了什么…然后就會覺得實現一個遞歸解法十分復雜，根本就無從下手。

相信很多初學者和我一樣，這是一個思維誤區，一定要走出來。既然遞歸是一個反復調用自身的過程，這就說明它每一級的功能都是一樣的，因此我們只需要關注一級遞歸的解決過程即可。

實在沒學過啥繪圖的軟件，就靈魂手繪了一波，哈哈哈勿噴。

如上圖所示，我們需要關心的主要是以下三點

整個遞歸的終止條件。

一級遞歸需要做什么？

應該返回給上一級的返回值是什么？

因此，也就有了我們解遞歸題的三部曲：

1. 找整個遞歸的終止條件：遞歸應該在什么時候結束？

2. 找返回值：應該給上一級返回什么信息？

3. 本級遞歸應該做什么：在這一級遞歸中，應該完成什么任務？

一定要理解這3步，這就是以后遞歸秒殺算法題的依據和思路。

但這么說好像很空，我們來以題目作為例子，看看怎么套這個模版，相信3道題下來，你就能慢慢理解這個模版。之后再解這種套路遞歸題都能直接秒了。

例1：求二叉樹的最大深度

先看一道簡單的Leetcode題目： Leetcode 104. 二叉樹的最大深度

題目很簡單，求二叉樹的最大深度，那么直接套遞歸解題三部曲模版：

找終止條件。 什么情況下遞歸結束？當然是樹為空的時候，此時樹的深度為0，遞歸就結束了。

找返回值。 應該返回什么？題目求的是樹的最大深度，我們需要從每一級得到的信息自然是當前這一級對應的樹的最大深度，因此我們的返回值應該是當前樹的最大深度，這一步可以結合第三步來看。

本級遞歸應該做什么。 首先，還是強調要走出之前的思維誤區，遞歸后我們眼里的樹一定是這個樣子的，看下圖。此時就三個節點：root、root.left、root.right，其中根據第二步，root.left和root.right分別記錄的是root的左右子樹的最大深度。那么本級遞歸應該做什么就很明確了，自然就是在root的左右子樹中選擇較大的一個，再加上1就是以root為根的子樹的最大深度了，然后再返回這個深度即可。

具體Java代碼如下：

class Solution {public int maxDepth(TreeNode root) {//終止條件：當樹為空時結束遞歸，并返回當前深度0if(root == null){return 0;}//root的左、右子樹的最大深度int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);//返回的是左右子樹的最大深度+1return Math.max(leftDepth, rightDepth) + 1;} } 當足夠熟練后，也可以和Leetcode評論區一樣，很騷的幾行代碼搞定問題，讓之后的新手看的一臉懵逼(這道題也是我第一次一行代碼搞定一道Leetcode題)： ```java class Solution {public int maxDepth(TreeNode root) {return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;} }

例2：兩兩交換鏈表中的節點

看了一道遞歸套路解決二叉樹的問題后，有點套路搞定遞歸的感覺了嗎？我們再來看一道Leetcode中等難度的鏈表的問題，掌握套路后這種中等難度的問題真的就是秒：Leetcode 24. 兩兩交換鏈表中的節點

直接上三部曲模版：

找終止條件。 什么情況下遞歸終止？沒得交換的時候，遞歸就終止了唄。因此當鏈表只剩一個節點或者沒有節點的時候，自然遞歸就終止了。

找返回值。 我們希望向上一級遞歸返回什么信息？由于我們的目的是兩兩交換鏈表中相鄰的節點，因此自然希望交換給上一級遞歸的是已經完成交換處理，即已經處理好的鏈表。

本級遞歸應該做什么。 結合第二步，看下圖！由于只考慮本級遞歸，所以這個鏈表在我們眼里其實也就三個節點：head、head.next、已處理完的鏈表部分。而本級遞歸的任務也就是交換這3個節點中的前兩個節點，就很easy了。

附上Java代碼：

class Solution {public ListNode swapPairs(ListNode head) {//終止條件：鏈表只剩一個節點或者沒節點了，沒得交換了。返回的是已經處理好的鏈表if(head == null || head.next == null){return head;}//一共三個節點:head, next, swapPairs(next.next)//下面的任務便是交換這3個節點中的前兩個節點ListNode next = head.next;head.next = swapPairs(next.next);next.next = head;//根據第二步：返回給上一級的是當前已經完成交換后，即處理好了的鏈表部分return next;} }

例3：平衡二叉樹

相信經過以上2道題，你已經大概理解了這個模版的解題流程了。

那么請你先不看以下部分，嘗試解決一下這道easy難度的Leetcode題（個人覺得此題比上面的medium難度要難）：Leetcode 110. 平衡二叉樹

我覺得這個題真的是集合了模版的精髓所在，下面套三部曲模版：

找終止條件。 什么情況下遞歸應該終止？自然是子樹為空的時候，空樹自然是平衡二叉樹了。

應該返回什么信息：

為什么我說這個題是集合了模版精髓？正是因為此題的返回值。要知道我們搞這么多花里胡哨的，都是為了能寫出正確的遞歸函數，因此在解這個題的時候，我們就需要思考，我們到底希望返回什么值？

何為平衡二叉樹？平衡二叉樹即左右兩棵子樹高度差不大于1的二叉樹。而對于一顆樹，它是一個平衡二叉樹需要滿足三個條件：它的左子樹是平衡二叉樹，它的右子樹是平衡二叉樹，它的左右子樹的高度差不大于1。換句話說：如果它的左子樹或右子樹不是平衡二叉樹，或者它的左右子樹高度差大于1，那么它就不是平衡二叉樹。

而在我們眼里，這顆二叉樹就3個節點：root、left、right。那么我們應該返回什么呢？如果返回一個當前樹是否是平衡二叉樹的boolean類型的值，那么我只知道left和right這兩棵樹是否是平衡二叉樹，無法得出left和right的高度差是否不大于1，自然也就無法得出root這棵樹是否是平衡二叉樹了。而如果我返回的是一個平衡二叉樹的高度的int類型的值，那么我就只知道兩棵樹的高度，但無法知道這兩棵樹是不是平衡二叉樹，自然也就沒法判斷root這棵樹是不是平衡二叉樹了。

因此，這里我們返回的信息應該是既包含子樹的深度的int類型的值，又包含子樹是否是平衡二叉樹的boolean類型的值。可以單獨定義一個ReturnNode類，如下：

class ReturnNode{boolean isB;int depth;//構造方法public ReturnNode(boolean isB, int depth){this.isB = isB;this.depth = depth;} }

本級遞歸應該做什么。 知道了第二步的返回值后，這一步就很簡單了。目前樹有三個節點：root，left，right。我們首先判斷left子樹和right子樹是否是平衡二叉樹，如果不是則直接返回false。再判斷兩樹高度差是否不大于1，如果大于1也直接返回false。否則說明以root為節點的子樹是平衡二叉樹，那么就返回true和它的高度。

具體的Java代碼如下：

class Solution {//這個ReturnNode是參考我描述的遞歸套路的第二步：思考返回值是什么//一棵樹是BST等價于它的左、右倆子樹都是BST且倆子樹高度差不超過1//因此我認為返回值應該包含當前樹是否是BST和當前樹的高度這兩個信息private class ReturnNode{boolean isB;int depth;public ReturnNode(int depth, boolean isB){this.isB = isB;this.depth = depth;}}//主函數public boolean isBalanced(TreeNode root) {return isBST(root).isB;}//參考遞歸套路的第三部：描述單次執行過程是什么樣的//這里的單次執行過程具體如下：//是否終止?->沒終止的話，判斷是否滿足不平衡的三個條件->返回值public ReturnNode isBST(TreeNode root){if(root == null){return new ReturnNode(0, true);}//不平衡的情況有3種：左樹不平衡、右樹不平衡、左樹和右樹差的絕對值大于1ReturnNode left = isBST(root.left);ReturnNode right = isBST(root.right);if(left.isB == false || right.isB == false){return new ReturnNode(0, false); }if(Math.abs(left.depth - right.depth) > 1){return new ReturnNode(0, false);}//不滿足上面3種情況，說明平衡了，樹的深度為左右倆子樹最大深度+1return new ReturnNode(Math.max(left.depth, right.depth) + 1, true);} }

一些可以用這個套路解決的題

暫時就寫這么多啦，作為一個高考語文及格分，大學又學了工科的人，表述能力實在差因此啰啰嗦嗦寫了一大堆，希望大家能理解這個很好用的套路。

下面我再列舉幾道我在刷題過程中遇到的也是用這個套路秒的題，真的太多了，大部分鏈表和樹的遞歸題都能這么秒，因為樹和鏈表天生就是適合遞歸的結構。

我會隨時補充，正好大家可以看了上面三個題后可以拿這些題來練練手，看看自己是否能獨立快速準確的寫出遞歸解法了。

Leetcode 101. 對稱二叉樹

Leetcode 111. 二叉樹的最小深度

Leetcode 226. 翻轉二叉樹：這個題的備注是最騷的。Mac OS下載神器homebrew的大佬作者去面試谷歌，沒做出來這道算法題，然后被谷歌面試官懟了：”我們90％的工程師使用您編寫的軟件(Homebrew)，但是您卻無法在面試時在白板上寫出翻轉二叉樹這道題，這太糟糕了。”

Leetcode 617. 合并二叉樹

Leetcode 654. 最大二叉樹

Leetcode 83. 刪除排序鏈表中的重復元素

Leetcode 206. 翻轉鏈表

總結

以上是生活随笔為你收集整理的3道题彻底搞定：套路解决递归问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。