《九日集训》(第九讲) 简单递归
文章目录
- 《九日集训》(第九讲) 简单递归
-
-
-
- [172. 阶乘后的零](https://leetcode-cn.com/problems/factorial-trailing-zeroes/)
-
-
- 题目详情:
- 思路：
-
- [1342. 将数字变成 0 的操作次数](https://leetcode-cn.com/problems/number-of-steps-to-reduce-a-number-to-zero/)
-
-
- 题目描述：
-
- [222. 完全二叉树的节点个数](https://leetcode-cn.com/problems/count-complete-tree-nodes/)
-
-
- 题目：
-
- [LCP 44. 开幕式焰火](https://leetcode-cn.com/problems/sZ59z6/)
-
-
- 题目：
- 思路：
-
- [397. 整数替换](https://leetcode-cn.com/problems/integer-replacement/)
-
-
- 题目：
-
- [938. 二叉搜索树的范围和](https://leetcode-cn.com/problems/range-sum-of-bst/)
- [剑指 Offer 55 - I. 二叉树的深度](https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/)
- [104. 二叉树的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)
- [226. 翻转二叉树](https://leetcode-cn.com/problems/invert-binary-tree/)
-
-
172. 阶乘后的零 题目详情: 给定一个整数
n ，返回 n! 结果中尾随零的数量。提示 `n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1。
f(n)=n/5+n/25+n/125+…
欧克，转换成递归。
class Solution {
public int trailingZeroes(int n) {
return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}
}
1342. 将数字变成 0 的操作次数 题目描述： 给你一个非负整数
num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。class Solution {
public int numberOfSteps(int num) {
int count=0;
if(num==0){
return 0;
}
while(num>0){
if((num & 1)== 0){//判断奇偶
num=num>>1;
}else{
num=num^1;
}
count++;
}
return count;
}
}
222. 完全二叉树的节点个数 题目： 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
class Solution {
public int countNodes(TreeNode root) {
if(root==null){
return 0;
}
return countNodes(root.left)+countNodes(root.right)+1;
}
}
这是暴力的方法，但是没有用到完全二叉树的特点。
完全二叉树的定义：它是一棵空树或者它的叶子结点只出在最后两层，若最后一层不满，只会出现在叶子结点的最左侧。
再来回顾一下满二叉的节点个数怎么计算，如果满二叉树的层数为h，则总节点数为：2^h - 1.
那么我们来对 root 节点的左右子树进行高度统计，分别记为 left 和 right，有以下两种结果：
- left == right。这说明，左子树一定是满二叉树，因为节点已经填充到右子树了，左子树必定已经填满了。所以左子树的节点总数我们可以直接得到，是 2^left - 1，加上当前这个 root 节点，则正好是 2^left。再对右子树进行递归统计。
- left != right。说明此时最后一层不满，但倒数第二层已经满了，可以直接得到右子树的节点个数。同理，右子树节点 +root 节点，总数为 2^right。再对左子树进行递归查找。
class Solution {
public int countNodes(TreeNode root) {
if(root == null){
return 0;
}
int left = countLevel(root.left);
int right = countLevel(root.right);
if(left == right){//判断是否满二叉树
return countNodes(root.right) + (1<LCP 44. 开幕式焰火 题目： 力扣挑战赛」开幕式开始了，空中绽放了一颗二叉树形的巨型焰火。
给定一棵二叉树 root 代表焰火，节点值表示巨型焰火这一位置的颜色种类。请帮小扣计算巨型焰火有多少种不同的颜色。
思路： HashSet集合的特点是重复，所以把所有节点存入HashSet，然后求长度就是颜色种类。
class Solution {
Set set = new HashSet<>();
public int numColor(TreeNode root) {
if(root == null) return 0;
set.add(root.val);
numColor(root.left);
numColor(root.right);
return set.size();
}
}
397. 整数替换 题目： 给定一个正整数 n ，你可以做如下操作：
【leetcode|《九日集训》(第九讲) 简单递归】如果 n 是偶数，则用 n / 2替换 n 。
如果 n 是奇数，则可以用 n + 1或n - 1替换 n 。
n 变为 1 所需的最小替换次数是多少？
class Solution {
public int integerReplacement(int n) {
int dp0 = 0, dp1 = 1;
//1 <= n <= 231 - 1数目太大会超时，变字符数组
char[] bits = Integer.toBinaryString(n).toCharArray();
for (int i = 1;
i < bits.length;
i++) {
int low = bits[i] - '0';
if (low == 0) {
dp1 = Math.min(dp0, dp1) + 2;
dp0++;
}
else {
dp0 = Math.min(dp0, dp1) + 2;
dp1++;
}
}
return dp0;
}
}
938. 二叉搜索树的范围和 题目：
给定二叉搜索树的根结点
root，返回值位于范围 [low, high] 之间的所有结点的值的和。思路：
二叉平衡树的特点：1、非叶子节点最多拥有两个子节点；2、非叶子节值大于左边子节点、小于右边子节点；3、树的左右两边的层级数相差不会大于1；4、没有值相等重复的节点。然后深度优先搜索。
class Solution {
public int rangeSumBST(TreeNode root, int low, int high) {
if(root == null){
return 0;
}
if(root.valhigh){
return rangeSumBST(root.left,low,high);
}
return root.val+rangeSumBST(root.right,low,high)+rangeSumBST(root.left,low,high);
}
}
剑指 Offer 55 - I. 二叉树的深度 题目：
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth,rightDepth)+1;
}
}
104. 二叉树的最大深度 题目：
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数
跟上面题一样
226. 翻转二叉树 题目：
翻转一棵二叉树。
输入：
4
/\
27
/ \/ \
13 69
输出：
4
/\
72
/ \/ \
96 31
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root==null){
return null;
}
//左右子树开始交换
TreeNode t=root.right;
root.right=root.left;
root.left=t;
//递归分别交换左子树，右子树。
invertTree(root.left);
invertTree(root.right);
return root;
}
}
return null;
}
//左右子树开始交换
TreeNode t=root.right;
root.right=root.left;
root.left=t;
//递归分别交换左子树，右子树。
invertTree(root.left);
invertTree(root.right);
return root;
}
}
推荐阅读
- 人工智能|一文看懂CV中的注意力机制
- Java进阶|Java进阶学习——数据结构基础（二）
- 数据结构|小肥柴慢慢手写数据结构（C篇）（3-2 Stack应用举例）
- 数据结构|数据结构与算法入门前必读
- 数据结构|数据结构与算法一篇帮助你吃下KMP算法
- 【数据结构·水滴计划】|【数据结构】一篇文章带你彻底吃透·算法复杂度
- JAVA后端|Java日期处理
- Letcode算法专篇|Java之有序集合&hashMap
- 广告主视角下的信息流广告算法探索