【LeetCode】HOT 100（22）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode】HOT 100（22）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题单介绍：

精选 100 道力扣（LeetCode）上最热门的题目，适合初识算法与数据结构的新手和想要在短时间内高效提升的人，熟练掌握这 100 道题，你就已经具备了在代码世界通行的基本能力。

题单介绍：

题目：538. 把二叉搜索树转换为累加树 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

题目：494. 目标和 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

写在最后：

题目：538. 把二叉搜索树转换为累加树 - 力扣（Leetcode）

【LeetCode】HOT 100（22）,LeetCode HOT 100,leetcode,算法,c++

题目的接口：

/**
 * 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 sum = 0;
    TreeNode* convertBST(TreeNode* root) {

    }
};

解题思路：

这道题并不难，

最难就难在读不懂题目是什么意思，读懂了就很好做了，

其实这道题目的关键点只有几个，

我把它们列出来：

1. 这是一个二叉搜索树

2. 累加树的性质：每个节点的值 = 所有比他大的节点的值 + 他本身的值

其实就是这两条性质，

而题目就是让我们把这一棵二叉搜索树转变成累加树。

所以我们只需要根据二叉搜索树的性质，从最大的节点开始搜索，

然依次累加值就行。

代码如下：

代码：

/**
 * 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 sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        if(root == nullptr) return nullptr;
        convertBST(root->right);
        sum += root->val;
        root->val = sum;
        convertBST(root->left);
        return root;
    }
};

过过过过啦！！！！

【LeetCode】HOT 100（22）,LeetCode HOT 100,leetcode,算法,c++

题目：494. 目标和 - 力扣（Leetcode）

【LeetCode】HOT 100（22）,LeetCode HOT 100,leetcode,算法,c++

题目的接口：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {

    }
};

解题思路：

这道题又是动态规划，

原本想用暴力枚举，好的失败了，有样例过不去

又是动态规划，可恶，

等我两周之后暑假了，有时间了，

马上去狂刷动态规划题目，把你拿下，

那现在我就简单用个搜索来写了，

搜索的逻辑比较简单，我就不解释了，

没有想到的是，我这段代码跑了一千多毫秒还给我过了。。。

代码如下：

代码：

class Solution {
public:
    int ans = 0;
    int findTargetSumWays(vector<int>& nums, int target) {
        dfs(nums, target, 0, 0);
        return ans;
    }
private:   
    void dfs(const vector<int>& nums, int target, int start, int sum) {
        if(sum == target && start == nums.size()) {
            ans++;
            return;
        }

        if(start >= nums.size()) return;

        dfs(nums, target, start + 1, sum + nums[start]);
        dfs(nums, target, start + 1, sum - nums[start]);
    }
};