【九日集训】第九天：简单递归

递归就是自己调用自己，例如斐波那契数列就是可以用简单递归来实现。

第一题 172. 阶乘后的零

https://leetcode.cn/problems/factorial-trailing-zeroes/description/
这一题纯粹考数学推理能力，我这种菜鸡看了好久都没有懂。
大概是这样的思路：
算n！中尾随0的数量第一时间想到的是10的因子，但到n = 5就不适用了，毕竟这里还是120包含1个0呢；
仔细观察可以发现有0的尾数阶乘结果中都包含2和5，恰好2*5 = 10我们只需要找成对的2和5就可以了。
但是举一个例子：
11! = 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 11 * (2 * 5) * 9 * (4 * 2) * 7 * (3 * 2) * (1 * 5) * (2 * 2) * 3 * (1 * 2) * 1
其中含有2的因子比5的次数多，且每出现一次5就会出现一次2，所以我们这里只需要找有多少个5即可。
但仔细观察可以发现，每隔5个数字出现一个5，每隔25个数字出现两个5，每隔125个数字出现3个5，以此类推
所以只需要按顺序加下去就得到最终的结果

int trailingZeroes(int n) {if(n < 5) return 0;return n / 5 + trailingZeroes(n / 5);
}

第二题 1342. 将数字变成 0 的操作次数

https://leetcode.cn/problems/number-of-steps-to-reduce-a-number-to-zero/description/
如果是0则返回0；
如果给定的数是偶数则除以2递归到下一层，同时将操作数 + 1；
否则减2同时操作数 + 1；

int numberOfSteps(int num) {if(num == 0) return 0;if(num % 2 == 0) {return numberOfSteps(num / 2) + 1;}return numberOfSteps(num - 1) + 1;
}

第三题 222. 完全二叉树的节点个数

https://leetcode.cn/problems/count-complete-tree-nodes/description/
算二叉树的节点个数，递归节点的左子树和右子树每次递归都将结果 + 1;
如果递归到节点为空则返回0；

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
int countNodes(struct TreeNode* root) {if(root == NULL) {return 0;}return countNodes(root->left) + countNodes(root->right) + 1;
}

第四题 LCP 44. 开幕式焰火

https://leetcode.cn/problems/sZ59z6/description/

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int Hash[1024];void transfer(struct TreeNode* root) {if(root) {Hash[root->val] = 1;transfer(root->left);transfer(root->right);}
}int numColor(struct TreeNode* root){int sum = 0;memset(Hash, 0, sizeof(Hash));transfer(root);for(int i = 1; i <= 1000; ++i) {if(Hash[i]) ++sum;}return sum;
}

第五题 397. 整数替换

https://leetcode.cn/problems/integer-replacement/description/

int min(int a, int b) {return a > b ? b : a;
}int integerReplacement(int n) {if(n == 1) return 0;if(n % 2 == 0) {return integerReplacement(n / 2) + 1;}return 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
}

第六题 938. 二叉搜索树的范围和

https://leetcode.cn/problems/range-sum-of-bst/description/
题目中给的是二叉搜索树，特点就是左小右大，因此如果当前root的val满足条件则将val加到return中，再加上左右子树满足条件的val和。
如果root的val大于high，则需要向左子树（小的一端）递归；
反之小于low向右子树递归；

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int rangeSumBST(struct TreeNode* root, int low, int high) {if(root == NULL) return 0;if(root->val > high) {return rangeSumBST(root->left, low, high);}if(root->val < low) {return rangeSumBST(root->right, low, high);}return root->val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low ,high);
}

第八题 LCR 175. 计算二叉树的深度

https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/description/

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/int max(int a, int b) {return a > b ? a : b;
}int calculateDepth(struct TreeNode* root) {if(root == NULL) return 0;return max(calculateDepth(root->left), calculateDepth(root->right)) + 1;
}

第九题 104. 二叉树的最大深度

这一题和上一题一样
https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

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

第十题 226. 翻转二叉树

https://leetcode.cn/problems/invert-binary-tree/description/

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
struct TreeNode* invertTree(struct TreeNode* root) {if(root == NULL) return NULL;struct TreeNode* left = invertTree(root->left);struct TreeNode* right = invertTree(root->right);root->left = right;root->right = left;return root;
}