leetcode刷题记录17（2023-08-25）【目标和(dfs、dp、背包) | 把二叉搜索树转换为累加树(反序中序遍历) | 二叉树的直径(df后序遍历) | 和为 K 的子数组(前缀和)】

迈不过友情╰ 2024-03-24 21:19 12阅读 0赞

## 494. 目标和 ##

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = \[2, 1\] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。  
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = \[1,1,1,1,1\], target = 3  
输出：5  
解释：一共有 5 种方法让最终目标和为 3 。  
\-1 + 1 + 1 + 1 + 1 = 3  
\+1 - 1 + 1 + 1 + 1 = 3  
\+1 + 1 - 1 + 1 + 1 = 3  
\+1 + 1 + 1 - 1 + 1 = 3  
\+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = \[1\], target = 1  
输出：1

提示：

1 <= nums.length <= 20  
0 <= nums\[i\] <= 1000  
0 <= sum(nums\[i\]) <= 1000  
\-1000 <= target <= 1000

每个元素有2种可能，所以就深搜，代码如下，但是时间复杂度为  O ( 2 n ) O(2^n) O(2n)，比较大。

class Solution {
        
        int dfs(vector<int>& nums, int target, int index) {
        
            if (index >= nums.size()) {
        
                return target == 0 ? 1 : 0;
            }
            int res = 0;
            res += dfs(nums, target - nums[index], index + 1);
            res += dfs(nums, target + nums[index], index + 1);
            return res;
        }
    public:
        int findTargetSumWays(vector<int>& nums, int target) {
        
            int res = dfs(nums, target, 0);
            return res;
        }
    };

利用背包问题来进行处理，假设我们设取负号的数字的和为 `neg`，这样取正数的和就是 `sum - neg`，再减去 `neg` 就有：

( s u m − n e g ) − n e g = t a r g e t (1) (sum-neg)-neg = target\\tag\{1\} (sum−neg)−neg=target(1)

sum和target都是常量，所以就有：

n e g = s u m − t a r g e t 2 (2) neg = \\frac\{sum-target\}\{2\}\\tag\{2\} neg=2sum−target(2)

因为 `sum - target` 是由 `2` 个 `neg` 加在一起的，因此需要为非负整数，否则直接返回 `0` 。

// 背包问题
    class Solution {
        
    public:
        int findTargetSumWays(vector<int>& nums, int target) {
        
            int sum = 0;
            for (auto num : nums) {
        
                sum += num;
            }
    
            // (sum - neg) - neg = target，所以 sum - target 一定是偶数
            if ((sum - target) < 0 || (sum - target) % 2 == 1) {
        
                return 0;
            }
            int neg = (sum - target) / 2;
            vector<int> dp(neg + 1);
            dp[0] = 1;
            for (int i = 0; i < nums.size(); i++) {
        
                for (int j = neg; j >= 0; j--) {
        
                    if (j - nums[i] >= 0) {
        
                        dp[j] = dp[j] + dp[j - nums[i]];
                    }
                }
            }
            return dp[neg];
        }
    };

## 538. 把二叉搜索树转换为累加树 ##

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键 小于 节点键的节点。  
节点的右子树仅包含键 大于 节点键的节点。  
左右子树也必须是二叉搜索树。  
注意：本题和 1038: [https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/][https_leetcode-cn.com_problems_binary-search-tree-to-greater-sum-tree] 相同

示例 1：

![在这里插入图片描述][a6cf8a17810a4a19a7672f411210c479.png]

输入：\[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8\]  
输出：\[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8\]

示例 2：

输入：root = \[0,null,1\]  
输出：\[1,null,1\]

示例 3：

输入：root = \[1,0,2\]  
输出：\[3,3,2\]

示例 4：

输入：root = \[3,2,4,1\]  
输出：\[7,9,4,10\]

提示：

树中的节点数介于 0 和  1 0 4 10^4 104 之间。  
每个节点的值介于  − 1 0 4 -10^4 −104 和  1 0 4 10^4 104 之间。  
树中的所有值 互不相同 。  
给定的树为二叉搜索树。

采用一个反序中序遍历的方法(为按照node->Value从大到小的顺序来访问)，同时按顺序记录当前的curSum，并赋值给当前节点。

// 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 {
        
        void dfs(TreeNode* root, int& curSum) {
        
            if (root == nullptr) {
        
                return;
            }
            int res = 0;
            dfs(root->right, curSum);
            curSum += root->val;
            root->val = curSum;
            dfs(root->left, curSum);
        }
    public:
        TreeNode* convertBST(TreeNode* root) {
        
            int curSum = 0;
            dfs(root, curSum);
            return root;
        }
    };

## 543. 二叉树的直径 ##

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

![在这里插入图片描述][b4080cfccdb342d084a0439b7e155b27.png]

输入：root = \[1,2,3,4,5\]  
输出：3  
解释：3 ，取路径 \[4,2,1,3\] 或 \[5,2,1,3\] 的长度。

示例 2：

输入：root = \[1,2\]  
输出：1

提示：

树中节点数目在范围  \[ 1 , 1 0 4 \] \[1, 10^4\] \[1,104\] 内  
 − 100 < = N o d e . v a l < = 100 -100 <= Node.val <= 100 −100<=Node.val<=100

主要思路就是进行后序遍历，同时记录左右子树的高度，将其高的一个+1作为返回值返回上一级父节点。

// 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 {
        
        int dfs(TreeNode* root, int& res) {
        
            if (root == nullptr) {
        
                return 0;
            }
            int deepLeft = dfs(root->left, res);
            int deepRight = dfs(root->right, res);
            res = max(res, deepLeft + deepRight);
            return max(deepLeft, deepRight) + 1;
        }
    public:
        int diameterOfBinaryTree(TreeNode* root) {
        
            int res = 0;
            dfs(root, res);
            return res;
        }
    };

## 560. 和为 K 的子数组 ##

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

示例 1：

输入：nums = \[1,1,1\], k = 2  
输出：2

示例 2：

输入：nums = \[1,2,3\], k = 3  
输出：2

提示：

1 < = n u m s . l e n g t h < = 2 ∗ 1 0 4 1 <= nums.length <= 2 \* 10^4 1<=nums.length<=2∗104  
 − 1000 < = n u m s \[ i \] < = 1000 -1000 <= nums\[i\] <= 1000 −1000<=nums\[i\]<=1000  
 − 1 0 7 < = k < = 1 0 7 -10^7 <= k <= 10^7 −107<=k<=107

这道题目的主要思路是前缀和，时间复杂度为O(n)，空间复杂度为O(n)，我的代码如下：

class Solution {
        
    public:
        int subarraySum(vector<int>& nums, int k) {
        
            unordered_map<int, int> mp;
            mp[0] = 1;
            vector<int> preSum(nums.size());
            preSum[0] = nums[0];
            int res = 0;
            if (preSum[0] == k) {
        
                res++;
            }
            mp[preSum[0]]++; // 一定要放在if后面，不然 k==0 的时候会出现bug
            for (int i = 1; i < preSum.size(); i++) {
        
                preSum[i] += preSum[i - 1] + nums[i];
                if (mp[preSum[i] - k] > 0) {
        
                    res += mp[preSum[i] - k];
                }
                mp[preSum[i]]++; // 一定要放在if后面，不然 k==0 的时候会出现bug
            }
            return res;
        }
    };

写完后，看了题解的代码，发现可以将内存优化道O(1)，发现自己的代码好笨，一方面是代码风格上的，另一方面是空间复杂度上的，都需要学习。

class Solution {
        
    public:
        int subarraySum(vector<int>& nums, int k) {
        
            unordered_map<int, int> mp;
            mp[0] = 1;
            int preSum = 0, res = 0;
            for (int i = 0; i < nums.size(); i++) {
        
                preSum += nums[i];
                if (mp[preSum - k] > 0) {
        
                    res += mp[preSum - k];
                }
                mp[preSum]++; // 一定要放在if后面，不然 k==0 的时候会出现bug
            }
            return res;
        }
    };

[https_leetcode-cn.com_problems_binary-search-tree-to-greater-sum-tree]: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/
[a6cf8a17810a4a19a7672f411210c479.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/c630392c269f46d080e47fd9728269ae.png
[b4080cfccdb342d084a0439b7e155b27.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/67e2e715a9814910a57cd9418e03a6fd.png