先序遍历改二叉搜索树 （二叉树的递归套路）
题目
本题为LC原题目 题目如下
题目分析
本题为一道经典的二叉树递归套路题目
我们只需要想好一个递归函数 之后让左右节点分别执行即可
我们这里想到的递归函数为
TreeNode* process(vector<int>& preorder , int L , int R)
该递归函数的意义为 给你数组的左右边界返回构造好的bst的头结点
之后我们只需要想边界条件
构造当前节点 构造左右子树即可
代码详解
class Solution {
public:// 该递归函数的意义为 给你数组的左右边界返回构造好的bst的头结点TreeNode* process(vector<int>& preorder , int L , int R) {if (L > R) {return nullptr;}TreeNode* root = new TreeNode(preorder[L]);// 找到左右边界的L和Rint i = 0;for ( i = L + 1 ; i < preorder.size(); i++) {if (preorder[i] > preorder[L]) {break;}}int nextright = i;// 1. 没有左边界 2.没有右边界root->left = process(preorder , L + 1 , nextright - 1);root->right = process(preorder , nextright , R);return root;}TreeNode* bstFromPreorder(vector<int>& preorder) {return process(preorder , 0 , preorder.size() - 1);}
};
返回一颗二叉树上有多少相等的子树 （二叉树的递归套路）
题目
给定一颗二叉树要求返回其最大相等子树的个数
题目分析
基本上所有的二叉树套路都可以使用我们题目一的解法来解决
我们首先假设一个函数
int process(TreeNode* root)
这个函数表示 我们给它一个根节点 它会返回我们二叉树上有多少相等的子树
之后只需要考虑边界条件 想左右子树即可
代码如下
代码详解
int process(TreeNode* root) {// 如果节点为空，返回 0if (root == nullptr) {return 0;}// 如果是叶子节点，本身就是一个子树，返回 1if (root->left == nullptr && root->right == nullptr) {return 1;}// 递归检查左右子树int lnLeftEqualSubtrees = process(root->left);int lnRightEqualSubtrees = process(root->right);// 如果左子树和右子树都存在且它们相等（值和结构相同）if (root->left != nullptr && root->right != nullptr && isSameTree(root->left, root->right)) {return 1 + lnLeftEqualSubtrees + lnRightEqualSubtrees;}// 否则只加上左右子树的相等子树数量return lnLeftEqualSubtrees + lnRightEqualSubtrees;}// 辅助函数：判断两棵树是否相同bool isSameTree(TreeNode* p, TreeNode* q) {if (p == nullptr && q == nullptr) {return true;}if (p == nullptr || q == nullptr || p->val != q->val) {return false;}return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}
编辑距离问题 （动态规划 样本对应模型）
题目
本题为LC原题 题目如下
题目分析
本题为经典的动态规划 样本对应模型 对于此模型 我们一般画出一张二维表即可解决
此二维表的含义为 dp[i][j] 表示word1的前i个字符可以变成word2的前j个字符能变化的最小次数
当i = 0的时候只有可能增加字符 所以第一行一定为 1 2 3 … M
当j= 0的时候只有可能删除字符 所以第一列一定是 1 2 3 4 … N
此时我们就可以推普遍情况了
既然可以增 删 换 那么我们的达成的方法就有三种
- 假设我们现在知道dp[i][j-1] 那么要得到dp[i][j] 只需要增加一个字符串
- 同理dp[i-1][j] 就只需要减少一个字符串
- dp[i-1][j-1]的情况比较特殊 此时我们要考虑他们i-1 j-1位置上的字符是否相等
最后取这三种可能性的最小值即可
代码详解
class Solution {
public:int minDistance(string word1, string word2) {int M = word1.size();int N = word2.size();int ans = 0;vector<vector<int>> dp(M + 1, vector<int>(N + 1, 0));for (int i = 0 ; i <= M ; i++) {dp[i][0] = i;}for (int j = 0; j <= N ; j++) {dp[0][j] = j;}for (int i = 1 ; i <= M ; i++) {for (int j = 1 ; j <=N ; j++) {int p1 = min(dp[i][j-1] , dp[i-1][j]) + 1;int p2 = word1[i-1] == word2[j-1] ? dp[i-1][j-1] : dp[i-1][j-1] + 1;dp[i][j] = min(p1 , p2);}}ans = dp[M][N];return ans;}};
