lC - 104. 二叉树的最大深度
难度:简单
题目描述
难度简单877收藏分享切换为英文接收动态反馈
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
MyCode
/**
* 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:
int maxDepth(TreeNode* root) {
if(root == nullptr) return 0;
else if(root->left == nullptr && root->right == nullptr) return 1;
else if(root->left != nullptr && root->right == nullptr)
return maxDepth(root->left) + 1;
else if(root->left == nullptr && root->right != nullptr)
return maxDepth(root->right) + 1;
else return std::max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
复杂度分析
-
时间复杂度:O(n),遍历二叉树所有元素就行
-
空间复杂度:O(hegiht),递归需要递归调用栈存储临时变量
TaCode
深度优先搜索
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
复杂度分析
- 时间复杂度:O*(*n),其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。
- 空间复杂度:O*(*height),其中height 表示二叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于二叉树的高度。
广度优先搜索
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
queue<TreeNode*> Q;
Q.push(root);
int ans = 0;
while (!Q.empty()) {
int sz = Q.size();
while (sz > 0) {
TreeNode* node = Q.front();Q.pop();
if (node->left) Q.push(node->left);
if (node->right) Q.push(node->right);
sz -= 1;
}
ans += 1;
}
return ans;
}
};
复杂度分析
- 时间复杂度:O*(*n),其中 n为二叉树的节点个数。与方法一同样的分析,每个节点只会被访问一次。
- 空间复杂度:此方法空间的消耗取决于队列存储的元素数量,其在最坏情况下会达到 O(n)O(n)。
总结
官方的题解更为简洁,是自己太菜了。还有第一次提交的时候竟然忘了处理root为nullptr的情况,淦。
LC - 62. 不同路径
难度:中等
题目描述
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例 1:
输入:m = 3, n = 7
输出:28
示例 2:
输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3:
输入:m = 7, n = 3
输出:28
示例 4:
输入:m = 3, n = 3
输出:6
提示:
1 <= m, n <= 100
- 题目数据保证答案小于等于
2 * 109
递归求解
本题使用动态规划更好一些,我在此给出递归的方法。
对象含义如下:
- pair<int, int > {m,n}:当前坐标
- map<pair<int, int>, int> map[{m,n}] : 表示起点到点{m,n}的路径数量。
递归思路如下:
- 递归终止条件:当点在最上一条边或最左一条边时,仅有一条路径
- 递归关系式:点{m,n}的路径个数 = 点{m - 1,n}的路径个数 + 点{m,n - 1}的路径个数
- 本题必须使用map存储数据,否则重复计算会造成超时。
Code
class Solution {
private:
int func(map<pair<int, int>, int> &map, int m, int n){
// 如果map没有{m,n}
if(map.find({m , n}) == map.end()){
// 递归终止条件 当点在最上一条边或最左一条边时,仅有一条路径
if(n == 1 || m == 1) map[{m , n}] = 1;
// 递归关系式 点{m,n}的路径 = 点{m - 1,n}的路径 + 点{m,n - 1}的路径
else map[{m, n}] = func(map, m - 1, n) + func(map, m, n - 1);
}
// 如果有,那么直接返回
return map[{m , n}];
}
public:
int uniquePaths(int m, int n) {
if(m <= 0 || n <= 0) return 0;
map<pair<int, int>, int> map;
return func(map, m, n);
}
};
总结
使用递归后注意优化,可以使用map或数组存储数据,类似于回溯中的剪枝。
剑指 - 16 数值的整数次方
难度中等
题目描述
实现 pow(x, n) ,即计算 x 的 n 次幂函数(即, x n x^n xn)。不得使用库函数,同时不需要考虑大数问题。
示例 1:
输入:x = 2.00000, n = 10
输出:1024.00000
示例 2:
输入:x = 2.10000, n = 3
输出:9.26100
示例 3:
输入:x = 2.00000, n = -2
输出:0.25000
解释:2-2 = 1/22 = 1/4 = 0.25
提示:
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
Code
class Solution {
private:
map<int, double> m;
double pow(double x, unsigned int n){
if(m.find(n) == m.end()){
if(n == 0){
m[0] = 1;
}
else if(n == 1){
m[1] = x;
}
else{
m[n] = pow(x, n /2) * pow(x, n - n /2);
}
}
return m[n];
}
public:
double myPow(double x, int n) {
if(n == 0) return 1;
else if(n > 0) {
return pow(x, n);
}else{
long int n_ = n;
unsigned int n__ = -n_;
// return 1/pow(x, -n);
return 1/pow(x, n__);
}
}
};
总结
注意第26行,若使用这段代码,对于测试用例 x = 1.00000,n = -2147483648,报错如下。
Line 26: Char 29: runtime error: negation of -2147483648 cannot be represented in type 'int'; cast to an unsigned type to negate this value to itself (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:36:29
n为int类型,四个字节,范围是 [ − 2 15 , 2 15 − 1 ] [-2^{15},2^{15} - 1] [−215,215−1]即为 [ − 2147483648 , 2147483647 ] [-2147483648,2147483647] [−2147483648,2147483647]。
error: negation of -2147483648 cannot be represented in type ‘int’; cast to an unsigned type to negate this value to itself (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:36:29
n为int类型,四个字节,范围是$[-2^{15},2^{15} - 1]$即为$[-2147483648,2147483647]$。
n = -2147483648取反超出了int的范围,所以本题中将 n 转换为unsigned int类型。