【算法】递归

递归

每一层只解决本层的问题，并假设下一层的结果就是factorial(n-1)，看两个例题：

阶乘

int factorial(int n){
	if(n <= 1) return 1;//第一步，确定终止条件
	int m = factorial(n-1);//第二步，递归并得到返回结果
	return n + m;//第三步，返回结果
//优化如下========>>>
int factorial(int n){
	n <= 1? return 1:return n + factorial(n-1);
}

斐波那契数列

基本递归

long long fibonacci(unsigned int n){
	if(n <= 0) return 0;
	if(n == 1) return 1;
	return fibonacci(n-1) + fibonacci(n-2);
}

它的时间复杂度是多少呢，易知递推公式为：$T(n)=T(n-1)+T(n-2)$ 显然不符合主定理的三种情况。一般通过画递归树来观察：

结论：$T(n)=O（2^n）$ ，空间复杂度$O(n)$ 因为最多有n个子函数被压栈了。

改进

斐波那契数列并不适合递归，因为有很多结点重复计算了。最好的方法是优化了的dp（双指针），时间复杂度为$O（n）$

long long fibonacci(unsigned int n){
	if(n <= 0) return 0;
	if(n == 1) return 1;
	long long p1 = 1,p2 = 0,ans = 0;
	for(unsigned int i=2;i<=n;i++){
		ans=p1+p2;
		p2=p1;//p1等价于f(n-2),因为p1是旧值
		p1=ans;//p1等价于f(n-1)
	}
	return ans;
}

再次改进

直接套数学公式计算结果，时间复杂度为$O(1)$

从尾到头打印链表

来源：剑6

struct ListNode{
	int value;
	ListNode* next;
}
void reversePrintLinklist(LinkNode* head){
	if(head != nullptr){
		if(head->next != nullptr){
			reversePrintLinklist(head->next);
		}
		cout << head->value;
	}
}

缺点：当链表非常长时，就会导致函数调用的层级很深，有可能导致函数调用栈溢出。循环+栈也能做。

538. 把二叉搜索树转换为累加树

给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater
Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

例如：

输入: 二叉搜索树:
5
/ \
2 13

输出: 转换为累加树:
18
/ \
20 13

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/convert-bst-to-greater-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    int num = 0;
    TreeNode* convertBST(TreeNode* root) {
        if(!root) return root;//终止条件
        convertBST(root->right);//处理右子树
        root->val += num;//num已经是右子树的累加值，处理根节点
        num = root->val;//更新累加值以方便左子树进行累加
        convertBST(root->left);//处理左子树
        return root;
    }
};

543. 二叉树的直径

copy的代码：

class Solution {
public:
    int maxLength=0;
    int maxDepth(TreeNode* root)
    {
        if(!root)
            return 0;
        int l=maxDepth(root->left);
        int r=maxDepth(root->right);
        if((l+r)>maxLength)
            maxLength=(l+r);
        return 1+max(l,r);
    }
        
    int diameterOfBinaryTree(TreeNode* root) 
    {
        if(!root)
            return 0;
        maxDepth(root);
        return maxLength;
    }
};