1. 递归

优化：尾递归https://www.jianshu.com/p/6bdc8e3637f2

1. 206. 反转链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//1. 递归
class Solution {
public:
//1.函数意义：反转单链表
    ListNode* reverseList(ListNode* head) {
        //2.结束条件
        if(head==NULL||head->next==NULL){
            return head;
        }
        //等价关系式
        //递归反转 子链表
        ListNode* node=reverseList(head->next);
        //改变节点的指向，反过来
        ListNode* tempNode=head->next;
        tempNode->next=head;
        head->next=NULL;
        return node;
    }
};
//2.双指针

2. 104. 二叉树的最大深度

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //1.函数意义：找到二叉树的最大深度
    int maxDepth(TreeNode* root) {
        //2.结束条件
        if(root==NULL){
            return 0;
        }
        // 等价关系式
        int m=maxDepth(root->left);
        int n=maxDepth(root->right);
        return m>n?m+1:n+1;
    }
};

3. 62. 不同路径

//超时
class Solution {
public:
    int uniquePaths(int m, int n) {
        return dfs(m-1,n-1);
    }
    //函数意义：从(0,0)到(i,j)的路径条数
    int dfs(int i,int j){
        //结束条件
        if(i==0||j==0){
            return 1;
        }
        //等价关系式
        return dfs(i-1,j)+dfs(i,j-1);
    }
};

//递归，超时
class Solution {
public:
    //函数意义：从(0,0)到(i,j)的路径条数
    int uniquePaths(int m, int n) {
        //结束条件
        if(m==1||n==1){
            return 1;
        }
        //等价关系式
        return uniquePaths(m-1,n)+uniquePaths(m,n-1);
    }
};

//优化。时间复杂度为 O(m * n)，空间复杂度为 (m * n)。 增加一个二维数组 保存已经计算过的结果
class Solution {
public:
    vector<vector<int>> arr;
    int uniquePaths(int m, int n) {
        arr.resize(m,vector<int>(n));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                arr[i][j]=0;
            }
        }
        return dfs(m-1,n-1);
    }
    //函数意义：从(0,0)到(i,j)的路径条数
    int dfs(int i,int j){
        //结束条件
        if(i==0||j==0){
            return 1;
        }
        //先查表
        if(arr[i][j]!=0){
            return arr[i][j];
        }

        //等价关系式
        return arr[i][j]=dfs(i-1,j)+dfs(i,j-1);
    }
};

4. 剑指 Offer 16. 数值的整数次方 和 50. Pow(x, n)

递归· 快速幂算法。O(nlogn)

class Solution {
public:
    //函数意义:计算x的n次方
    double myPow(double x, int n) {
        //结束条件
        if(n==0){
            return 1;
        }
        if(n==1){
            return x;
        }
        if(n==-1){
            return 1/x;
        }
        //找等价关系式
        double temp=0;
        temp=myPow(x, n >> 1);   
        temp*=temp;   //写成 temp=myPow(x, n >> 1)*myPow(x, n >> 1);会超时，计算量过大。 
        if(n&1==1){
            temp*=x;
        }
        return temp;
    }
};


//非递归
class Solution {
public:
    //函数意义:计算x的n次方
    double myPow(double x, int n) {
        double result=1;
        if(x==0){
            return 0;
        }
        long b=n;    //考虑到 2^31 次方的问题（取相反数后也是 2^31 次方），故需要用一个 long 类型来接收 n，然后再去取相反数。
        if(n<0){
            b=-b;
            x=1/x;
        }
        while(b>0){
            if((b&1)==1)  {  //是奇数
                result*=x;
            }
            x*=x;   //x自乘
            b=b>>1;   //n*2
        }
        return result;
    }
};

5. 326. 3 的幂

//1.递归
class Solution {
public:
    //meaning
    bool isPowerOfThree(int n) {
        //ending
        if(n==0||n==2){
            return false;
        }else if(n==1||n==3){
            return true;
        }

        //condition
        if(n%3==0){
            return isPowerOfThree(n/3);
        }
        return false;
    }
};   //2^31-1=2147483647

//2.非递归  试除法
class Solution {
public:
    bool isPowerOfThree(int n) {
        while( n>0 && n%3==0){
            n/=3;
        }
        return n==1;
    }
};

6. 234. 回文链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

//递归
class Solution {
public:
    ListNode* first;
    bool isPalindrome(ListNode* head) {
        first=head;
        return dfs(first);
    }

    bool dfs(ListNode* last){
        //ending
        if(last!=NULL){
            //不断压入栈中
            if(!dfs(last->next)){
                return false;
            }
            //当到最后一个节点时，开始弹出，比较栈顶元素和 first所指向的元素，递归栈的栈顶元素不断往后弹出，first也往后移。
            if(last->val!=first->val){
                return false;
            }
            first=first->next;
        }
        return true;
    }
};

7. 342. 4的幂 231. 2 的幂

//递归
class Solution {
public:
    //meaning
    bool isPowerOfFour(int n) {
        //ending
        if(n==1){
            return true;
        }
        //condition
        if(n&&n%4==0){
            return isPowerOfFour(n/4);
        }
        return false;
    }
};

//非递归，试除法
class Solution {
public:
    bool isPowerOfFour(int n) {
        while(n&&n%4==0){
            n/=4;
        }
        return n==1;
    }
};

8. 509. 斐波那契数

class Solution {
public:
//meaning
    int fib(int n) {
        //ending
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        //condition
        return fib(n-1)+fib(n-2);
    }
};

//递归优化,尾递归法
class Solution {
public:
    vector<int> arr;
    int tail(int n,int ret1,int ret2){
        if(n==0)
            return ret1;
        return tail(n-1,ret2,ret1+ret2);
    }
    int fib(int n) {
        return tail(n,0,1);
    }
};