算法06-遞歸的實現(xiàn)、特性以及思維要點

《算法練習-文章匯總》

樹的面試題一般都是遞歸

1.節(jié)點的定義
2.重復性(自相似性)

遞歸Recursion

遞歸-循環(huán)
通過函數(shù)體來進行的循環(huán)
遞歸和循環(huán)沒有明顯的邊界
1.從前有個山
2.山里有個廟
3.廟里有個和尚講故事
4.返回1
《盜夢空間》
1.向下進入到不同的夢境中；向上又回到原來一層
2.通過聲音同步回到上一層
3.每一層的環(huán)境和周圍的人都是一根拷貝、主角等幾個人穿越不同層級的夢境(發(fā)生和攜帶變化)

階乘

n! = 123...n;

def Factorial(n):
if n<=1
return 1;
return n*Factorial(n-1);

I 遞歸終結條件
II 處理當前層邏輯
III 下探到下一層
IV 清理當前層

Python代碼模板

def recursion(level,param1,param2,...)
# recursion terminator
if level > MAX_LEVEL;
process_result
return

#process logic in current level
process(level,data...)

# drill down
self.recursion(level+1,p1,...)

# reverse the current level status if needed

Java代碼模板

public void recur(int level,int param){
   //ternimator
   if(level>MAX_LEVEL){
   //process result
   return;
   }
   
   //process current logic
   process(level,param);
   
   //drill down
   recur(level:level+1,newParam);
   
   //restore current status
}

思維要點

1.不要人肉進行遞歸(最大誤區(qū))----直接看函數(shù)本身開始寫
2.找到最近最簡方法，將其拆解成可重復解決的問題(重復子問題)
3.數(shù)學歸納法思維

爬樓梯

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數(shù)。

示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。

  1. 1 階 + 1 階
  2. 2 階
    示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。

  1. 1 階 + 1 階 + 1 階
  2. 1 階 + 2 階
  3. 2 階 + 1 階

方法一:傻遞歸

class Solution {
    public int climbStairs(int n) {
        //遞歸結束條件
        if(n <= 2){
            return n;
        }
        return climbStairs(n-1)+climbStairs(n-2);
    }
}
復雜度分析
時間復雜度：O(2^n)
空間復雜度：O(n)

方法二:輔助數(shù)組

class Solution {
    public int climbStairs(int n) {
         if(n<=2)
         return n;
         int[] array = new int[n];
         for(int i=0;i<n;i++){
             if(i<=1){
                 array[i] = i + 1;
             }else{
                 array[i] = array[i-1]+array[i-2];
             }
         }
         return array[n - 1];
    }
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(n)

方法三:輔助緩存

class Solution {
    public int climbStairs(int n) {
         if(n<=2)
         return n;
         int f1=1,f2=2,f3=3;
         int i = 3;
         while(i <= n){
             f3 = f2 + f1;
             f1 = f2;
             f2 = f3;
             i++;
         }
        return f3;
    }
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(n)

方法四:動態(tài)規(guī)劃

class Solution {
    public int climbStairs(int n) {
         int p = 0,q = 0,r = 1;
         for(int i = 1;i <= n; i++){
             p = q;
             q = r;
             r = p + q;
         }
         return r;
    }
}
復雜度分析
時間復雜度：循環(huán)執(zhí)行n次，每次花費常數(shù)的時間代價，故漸進時間復雜度為 O(n)。
空間復雜度：這里只用了常數(shù)個變量作為輔助空間，故漸進空間復雜度為O(1)。

括號生成

數(shù)字 n 代表生成括號的對數(shù)，請你設計一個函數(shù)，用于能夠生成所有可能的并且 有效的 括號組合。
示例：
輸入：n = 3
輸出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

public class Solution {
    private List<String> result;
    public List<String> generateParenthesis(int n){
        result = new ArrayList<>();
        _generate(0,0,n,"");
        return result;
    }

    private void _generate(int left, int right, int max, String s) {
        //terminator
        if (left == max && right == max){
            result.add(s);
            return;
        }
        //process logic in current level

        //drill down
        if (left <= max)
        _generate(left+1,right,max,s + "(");
        if (right < left)
        _generate(left,right+1,max,s + ")");
        //reverse status
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.generateParenthesis(3));
    }
}
//輸出
[((())), (()()), (())(), ()(()), ()()()]

驗證二叉搜索樹

https://leetcode-cn.com/problems/validate-binary-search-tree/

二叉搜索樹.jpg

需要注意的是不僅左子結點（右子結點）需要小于（大于）該結點，而且整個左子樹（右子樹）的所有的元素都應該小于（大于）該結點。所以我們在遍歷的同時需要同結點的上界和下界比較。

方法一:遞歸 + 前序遍歷

上述的思路可以通過遞歸的方法實現(xiàn)，將當前結點的值與上下界進行比較，然后在對左右子樹進行遞歸。
過程如圖所示：


上下界.jpg
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isValidBST(struct TreeNode* root) {
        return helper(root,LONG_MIN,LONG_MAX);
    }
    bool helper(struct TreeNode* node,long long lower,long long upper){
        if(node == NULL) return true;
        long long value = node->val;
        if(value <= lower || value >= upper)return false;
        return helper(node->left,lower,value) && helper(node->right,value,upper);
    }
};

方法二:遞歸 + 中序遍歷

我們也可以采用中序遍歷的方式，因為中序遍歷后的二叉搜索樹是有序的，所以只需判斷一次當前結點的值即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* pre = NULL;
    bool isValidBST(TreeNode* root) {
        if(root == NULL) return true;
        if(!isValidBST(root->left)) return false;
        if(pre != NULL && pre->val >= root->val) return false;
        pre = root;
        return isValidBST(root->right);
    }
};

方法三:棧 + 中序遍歷

基于棧實現(xiàn)中序遍歷。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    long long lower = LONG_MIN;
    stack<TreeNode*> s;
    bool isValidBST(TreeNode* root) {
        while(root != NULL || !s.empty()){
               while(root != NULL){
                  s.push(root);
                  root = root->left;
               }
               root = s.top();
               s.pop();
               if(root->val <= lower) return false;
               lower = root->val;
               root = root->right;
        }
        return true;
    }
};

接下來講解一下如何使用棧實現(xiàn)前中后序遍歷，以棧實現(xiàn)中序遍歷為例，過程如下圖：

棧.jpg

棧實現(xiàn)中序遍歷模板及關鍵點：


棧中序遍歷.jpg
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(root == NULL) return ret;
        stack<TreeNode *> s;
        while(root!= NULL || !s.empty()){
            while(root != NULL){
                s.push(root);
                root = root->left;
            }
            root = s.top();
            s.pop();
            ret.push_back(root->val);
            root = root->right;
        }
        return ret;
    }
};

棧實現(xiàn)前序遍歷代碼如下：


前序遍歷.jpg
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(root == NULL) return ret;
        stack<TreeNode *> s;
        s.push(root);
        while(!s.empty()){
            TreeNode * node = s.top();
            ret.push_back(node->val);
            s.pop();
            if(node->left != NULL) s.push(node->left);
            if(node->right != NULL) s.push(node->right);
        }
        return ret;
    }
};

棧實現(xiàn)后序遍歷代碼如下：


后序遍歷.jpg
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ret;
        if(root == NULL) return ret;
        stack<TreeNode *> s;
        s.push(root);
        while(!s.empty()){
            TreeNode * node = s.top();
            ret.push_back(node->val);
            s.pop();
            if(node->right != NULL) s.push(node->right);
            if(node->left != NULL) s.push(node->left);
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }
};

層序遍歷

層序遍歷非常好理解，就是將二叉樹的每一層分遍歷，直到最后所有的結點全部遍歷完成，這里我們需要的輔助數(shù)據(jù)結構是隊列，因為需要用到隊列先進先出的特性。


層序遍歷.jpg

模板代碼如下：


層序遍歷模板.jpg
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelorderTraversal(TreeNode* root) {
        vector<vector<int>> ret;
        if(root == NULL) return ret;
        queen<TreeNode *> q;
        q.push(root);
        while(!q.empty()){
            int count = q.size();
            ret.push_back(vector<int> ());
            for(int i = 1;i <= count;i++){
             TreeNode * node = q.front();
             q.pop();
             ret.back().push_back(node->val);
             if(node->left)q.push(node->left);
             if(node->right)q.push(node->right);
            }
        }
        return ret;
    }
};

二叉樹的最大深度

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

二叉樹的最大深度.jpg

二叉樹最大深度代碼.jpg

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        int left_Depth = maxDepth(root->left);
        int right_Depth = maxDepth(root->right);
        return (left_Depth > right_Depth? left_Depth:right_Depth)+1;
    }
};

《驗證二叉搜索樹》和《二叉樹的最大深度》。

最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

友情鏈接更多精彩內(nèi)容