- 1. 深度优先、广度优先搜索
- JZ 13 机器人的运动范围
- JZ 26 树的子结构
- JZ 27 二叉树的镜像
- JZ 28 对称的二叉树
- JZ 34 二叉树中和为某一值的路径
- JZ 68 II. 二叉树的最近公共祖先
- JZ 68 - I. 二叉搜索树的最近公共祖先
- JZ 67 把字符串转换成整数
秋招对我好点！ 1. 深度优先、广度优先搜索 JZ 13 机器人的运动范围
题目链接
分析： 由于机器可以向右或者向下运动，并且题目求解的是能够到达的格子数，而不是分析运动到右下角会出现的一些问题，因此我们选择广度优先搜索，而不是深度优先搜索。
广度优先搜索类似于二叉树的层次遍历（每次分析上一个节点能达到的所有情况），选择队列queue进行辅助
深度优先搜索由于是递归问题，所以可以使用栈来辅助，递归问题从本质上来说就是利用栈来实现的，这也是为什么递归可以保留上一次递归的信息（先进后出的栈功不可没！）
class Solution {
public:
int getNum(int x){
int res = 0;
while(x!=0){
res += x%10;
x/=10;
}
return res;
}
int movingCount(int m, int n, int k) {
// 使用广度优先搜索
// 使用队列来辅助
if(k==0) return 1;
queue> q;
vector> visited(m,vector(n,0));
int ans = 1;
q.push(make_pair(0,0));
visited[0][0] = 1;
int dx[2] = {0,1};
int dy[2] = {1,0};
while(!q.empty()){
auto [x,y] = q.front();
q.pop();
// 广度有限搜索
for(int i=0;i<2;++i){
int tx = x + dx[i];
int ty = y + dy[i];
if(tx<0 || tx>=m || ty<0 || ty>=n || visited[tx][ty] || getNum(tx) + getNum(ty)>k) continue;
q.push(make_pair(tx,ty));
ans++;
visited[tx][ty] = 1;
}
}
return ans;
}
};
JZ 26 树的子结构
题目链接
分析： 对于树的子结构问题，一般都采用递归。
主要步骤有两个：
- 在树 A 中找到和树 B 的根节点的值一样的节点 p
- 判断树 A 中以 p 为根节点的子树是不是包含和树 B 一样的结构
class Solution {
public:
bool isSub(TreeNode* root1, TreeNode* root2){
if(!root2) return true;
if(!root1 || root1->val != root2->val) return false;
return isSub(root1->left,root2->left) && isSub(root1->right,root2->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
// 使用递归
if(!A || !B) return false; // 如果A B为nullptr的话 返回false
return isSub(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B);
}
};
JZ 27 二叉树的镜像
题目链接
分析： 将root的两个子树先保存下来，一直递归到最深处，进行交换。
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(!root) return NULL;
TreeNode* left = mirrorTree(root->left);
TreeNode* right = mirrorTree(root->right);
root->right = left;
root->left =right;
return root;
}
};
JZ 28 对称的二叉树
题目链接
分析： 如果一棵二叉树和它的镜像一样，那么它是对称的。
因此判断条件可视为 两个树在什么情况下是镜像对称的：
- 它们的两个根结点具有相同的值
- 每个树的右子树都与另一个树的左子树镜像对称
class Solution {
public:
bool check(TreeNode* root1,TreeNode*root2){
if(!root1 && !root2) return true;
if(!root1 || !root2) return false;
return root1->val==root2->val && check(root1->right,root2->left) && check(root2->right,root1->left);
}
bool isSymmetric(TreeNode* root) {
// 根节点有相同的值 并且一个树的左子树和另一棵树的右子树镜像对称
return check(root,root);
}
};
JZ 34 二叉树中和为某一值的路径
题目链接
分析： 想都不要想，这题肯定采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。
class Solution {
private:
vector> result;
vector path;
public:
void dfs(TreeNode* root,int target,int num){
// 递归结束
if(!root) return;
path.push_back(root->val);
num+=root->val;
if(!root->left && !root->right && num==target){
result.push_back(path);
}
dfs(root->left, target,num);
dfs(root->right, target,num);
path.pop_back();
}
vector> pathSum(TreeNode* root, int target) {
// 使用递归 深度优先搜索
dfs(root,target,0);
return result;
}
};
JZ 68 II. 二叉树的最近公共祖先
题目链接
分析：
最近工作祖先存在三种情况：
- 左子树和右子树都存在一个
- 只存在与左子树中
- 只存在右子树中
先搜索到最深处，再递归回来，进行判断。
**需要时刻记住的是：**递归的返回值是什么！
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 使用dfs
if(root==nullptr || root == p || root == q) return root; // 递归结束
// 递归需要时刻记住的是 返回的是什么
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(left!=nullptr && right!=nullptr) return root; // 左子树和右子树都不为空
if(left==nullptr) return right; // 左子树为空 全在右子树
if(right==nullptr) return left; // 右子树为空 全在左子树
return nullptr;
}
};
JZ 68 - I. 二叉搜索树的最近公共祖先
题目链接
分析：
可以用二分查找，也可以使用递归求解！
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 二叉树是一样的
// 使用递归
// 返回值是最近公共祖先
if(root==nullptr) return nullptr;
if(root==p || root ==q) return root;
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(left==nullptr && right==nullptr) return nullptr;
if(left==nullptr) return right;
if(right==nullptr) return left;
return root;
}
};
JZ 67 把字符串转换成整数
题目链接
分析：
耐心去分析，把所有情况都分析到位了！
class Solution {
public:
int strToInt(string str) {
// 练习一下自己的逻辑能力
long long number = 0;
int size = str.size();
// 去除空格
int i=0;
while(i'9' || str[i]<'0')) return 0;
else{
if(str[i]=='+'){
i++;
}else if(str[i]=='-'){
i++;
flag = false;
}
while(i='0'){
number *=10;
number+=str[i]-'0';
if(number>INT_MAX) break;
i++;
}
}
if(!flag) number*=-1;
// else if(str[i]=='+'){
// i++;
// while(i='0'){
// number *=10;
// number+=str[i]-'0';
// if(number>INT_MAX) break;
// i++;
// }
// }
// else if(str[i]=='-'){
// cout<<"1"<='0'){
// number *=10;
// number+=str[i]-'0';
// if(number>INT_MAX) break;
// i++;
// }
// number*=-1;
// cout<
// while(i='0'){
// number *=10;
// number+=str[i]-'0';
// if(number>INT_MAX) break;
// i++;
// }
// }
if(number>=INT_MAX) return INT_MAX;
if(number<=INT_MIN) return INT_MIN;
return (int)number;
}
};
