算法-递归的实现、特性以及思维要点

作者: 一亩三分甜 | 来源:发表于2020-08-13 01:26 被阅读0次

树的面试题一般都是递归

1.节点的定义
2.重复性(自相似性)

递归Recursion

递归-循环
通过函数体来进行的循环
递归和循环没有明显的边界
1.从前有个山
2.山里有个庙
3.庙里有个和尚讲故事
4.返回1
《盗梦空间》
1.向下进入到不同的梦境中；向上又回到原来一层
2.通过声音同步回到上一层
3.每一层的环境和周围的人都是一根拷贝、主角等几个人穿越不同层级的梦境(发生和携带变化)

阶乘

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.不要人肉进行递归(最大误区)----直接看函数本身开始写
2.找到最近最简方法，将其拆解成可重复解决的问题(重复子问题)
3.数学归纳法思维

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶
2 阶
示例 2：

输入： 3
输出： 3
解释：有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
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)

方法二:辅助数组

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)

方法四:动态规划

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;
    }
}
复杂度分析
时间复杂度：循环执行n次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。
空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为O(1)。

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例：
输入：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
需要注意的是不仅左子结点（右子结点）需要小于（大于）该结点，而且整个左子树（右子树）的所有的元素都应该小于（大于）该结点。所以我们在遍历的同时需要同结点的上界和下界比较。

方法一:递归 + 前序遍历

上述的思路可以通过递归的方法实现，将当前结点的值与上下界进行比较，然后在对左右子树进行递归。
过程如图所示：

上下界.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);
    }
};

方法三:栈 + 中序遍历

基于栈实现中序遍历。

/**
 * 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;
    }
};

接下来讲解一下如何使用栈实现前中后序遍历，以栈实现中序遍历为例，过程如下图：

栈.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<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;
    }
};

栈实现前序遍历代码如下：

前序遍历.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;
    }
};

栈实现后序遍历代码如下：

后序遍历.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;
    }
};

层序遍历

层序遍历非常好理解，就是将二叉树的每一层分遍历，直到最后所有的结点全部遍历完成，这里我们需要的辅助数据结构是队列，因为需要用到队列先进先出的特性。

层序遍历.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;
    }
};

《验证二叉搜索树》和《二叉树的最大深度》。