遞歸結題三部曲
何為遞歸？程序反復調用自身即是遞歸。
我自己在剛開始解決遞歸問題的時候，總是會去糾結這一層函數做了什么，它調用自身后的下一層函數又做了什么…然后就會覺得實現一個遞歸解法十分復雜，根本就無從下手。
相信很多初學者和我一樣，這是一個思維誤區，一定要走出來。既然遞歸是一個反復調用自身的過程，這就說明它每一級的功能都是一樣的，因此我們只需要關注一級遞歸的解決過程即可。
從圖中可以看出，遞歸是先遞后歸，自下往上處理。
如上圖所示，我們需要關心的主要是以下三點：
- 整個遞歸的終止條件。
- 一級遞歸需要做什么？
- 應該返回給上一級的返回值是什么？
因此，也就有了我們解樹形遞歸的三部曲 ：
- 找到整個遞歸的終止條件：遞歸應該在什么時候結束？
- 找返回值：本級應該給上一級返回什么信息？
- 本級遞歸應該做什么：在這一級遞歸中，應該完成什么任務？
定要理解這3步，這就是以后遞歸秒殺算法題的依據和思路。
但這么說好像很空，我們來以題目作為例子，看看怎么套這個模版，相信5道題下來，你就能慢慢理解這個模版。之后再解這種套路遞歸題都能直接秒了
例1：求二叉樹的最大深度
先看一道簡單的LEEDCode題目：104. 二叉樹的最大深度
直接套遞歸結題三部曲：
- 找終止條件：什么情況下不在遞歸下去？當然是樹為空的時候，此時樹的深度為0，遞歸就結束了。
- 找返回值：本級應該返回給上一級什么信息？題目是要我們求最大深度，我們需要返回的當然是當前級對應的樹的最大深度，比如下圖的右邊，返回值應該是root的最大深度，root的下一級有l和r
- 本級應該做什么：首先，還是強調要走出之前的思維誤區，遞歸后我們眼里的樹一定是下圖右邊。此時就三個節點：root、root.left、root.right，根據第二步，root.left和root.right分別記錄的是root的左右子樹的最大深度，那么本級遞歸應該做的就很明確了，那就是在root的左右子樹中選擇一個較大的一個，加上1就是root的最大深度了，然后再返回這個深度即可
int maxDepth(struct TreeNode* root){if(root==NULL){return 0;}/* root的左右子樹最大高度 */int leftDepth = maxDepth(root->left);int rightDepth = maxDepth(root->right);/* 返回值是左右子樹最大深度加1 */return leftDepth>rightDepth?(leftDepth+1):(rightDepth+1);
}
例2 ：兩兩交換鏈表中的結點。
看了一道遞歸套路解決二叉樹的問題后，有點套路搞定遞歸的感覺了嗎？我們再來看一道Leetcode中等難度的鏈表的問題，掌握套路后這種中等難度的問題真的就是秒：Leetcode 24. 兩兩交換鏈表中的節點
三部曲模板：
- 找終止條件：什么情況下終止？沒有辦法交換的時候，遞歸就停止。因此當鏈表只剩一個結點或者沒有幾點的時候，自然遞歸就終止了。
- 找返回值：本級希望向上一級返回的信息是什么？由于我們的目的是兩兩交換鏈表中相鄰的結點，因此自然希望交換給上一級遞歸的是本級已經處理好的鏈表。
- 本級應該做什么？題目讓交換相鄰兩個節點，所以我們應該交換相鄰兩個節點，涉及三個結點，兩個指針，head結點，head->next結點，以及head->next->next后面已經處理好的鏈表，我們看做一個結點。本級遞歸的任務就是交換這3個結點中的前兩個結點。
struct ListNode* swapPairs(struct ListNode* head) {/* 終止條件 */if (head == NULL || head->next == NULL) {return head;}/* 獲取head->next結點 */struct ListNode*next = head->next;/* swapPairs(next->next)代表已經處理好的鏈表，交換兩個節點，我們要讓head指向這個結點 */head->next = swapPairs(next->next);/* next指向head結點 此時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這棵樹是不是平衡二叉樹了。
因此，我們定義一個結構體，該結構體包含結點的深度，以及該節點是不是平衡二叉樹。
struct inf{int length;//當前節點的長度bool isB; //當前節點是不是平衡樹};
返回值就是當級節點的深度以及該節點是不是平衡二叉樹。如果不是平衡二叉樹，返回值的深度為0
- 本級遞歸該做什么？知道了第二步的返回值后，我們應該先獲得當前節點左右子樹的struct inf信息，即左右子樹的深度以及是不是平衡二叉樹。然后判斷左右子樹是不是平衡二叉樹以及高度差是否大于1。
struct inf{int length;//當前節點的長度bool isB; //當前節點是不是平衡樹};
struct inf *tru ; /* 表示一個節點的初始狀態是平衡二叉樹 */
struct inf *fal ; /* 表示不是平衡二叉樹 */struct inf *getInf(struct TreeNode *root)
{if(root==NULL){return tru; }/* 獲取左右子樹的深度以及是不是平衡二叉樹信息 */struct inf *right = getInf(root->right);struct inf *left = getInf(root->left);/*判斷左右子樹是不是平衡二叉樹*/if(right->isB == false || left->isB == false ){return fal;}/* 高度差是否大于1 */if(abs(right->length-left->length)>1){return fal;}/* 返回值左右子樹深度最大值加1并且是平衡二叉樹 */struct inf *ret = (struct inf *)malloc(sizeof(struct inf));ret->length = fmax(left->length,right->length)+1;ret->isB = true;return ret;}bool isBalanced(struct TreeNode* root){tru = (struct inf *)malloc(sizeof(struct inf));tru->length=0;tru->isB=true;fal = (struct inf *)malloc(sizeof(struct inf));fal->length=0;fal->isB = false;struct inf *ret = getInf(root);if(ret->isB==true)return true;elsereturn false;
}
)
