538. 把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
注意：本题和 1038: 力扣 相同
示例 1：
输入：[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和104之间。 - 每个节点的值介于
-104和104之间。 - 树中的所有值 互不相同 。
- 给定的树为二叉搜索树。
思路：
不难发现，图中的顺序就是 右、中、左 遍历二叉树，所以只要按这个顺序放入队列中，再依次取出相加即可。
代码：
/**
* 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:
queue<TreeNode*> q;
void bianli(TreeNode* p)
{
if(p==nullptr)return;
if(p->right)bianli(p->right);
q.push(p);
bianli(p->left);
}
TreeNode* convertBST(TreeNode* root) {
if(root==nullptr)return nullptr;
bianli(root);
TreeNode* p;
p=q.front();
int sum=p->val;
q.pop();
while(q.size())
{
p=q.front();
q.pop();
sum=sum+p->val;
p->val=sum;
}
return root;
}
};543. 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
思路：
就是对于每个结点看左子树最深处到右子树最深处加起来的和，选最大的结点。
代码：
/**
* 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 mmax=0;
int dfs(TreeNode* root)
{
if(root==nullptr)return 0;
int L=dfs(root->left);
int R=dfs(root->right);
mmax=max(mmax,L+R);
return max(L,R)+1;
}
int diameterOfBinaryTree(TreeNode* root) {
if(root==nullptr)return 0;
dfs(root);
return mmax;
}
};560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2
示例 2：
输入：nums = [1,2,3], k = 3 输出：2
提示：
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
思路：
哈希+前缀和
代码：
class Solution {
public:
int sum=0;
unordered_map<int,int> m;
int subarraySum(vector<int>& nums, int k) {
//if(nums[0]==k)sum++;
int pre=0;
m[pre]=1;
for(int i=0;i<nums.size();i++)
{
pre=pre+nums[i];
if(m.find(pre-k)!=m.end())sum+=m[pre-k];
m[pre]++;
}
return sum;
}
};
