108.将有序数组转换成二叉搜索树
给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵
平衡二叉搜索树
思路: 二叉搜索树的中序遍历就是有序升序数组，所以想要将它在转换成二叉树，我想到的方法就是通过递归来做，通过中间节点找到二叉搜索树的根节点，然后根据left和right双指针逐层递归构造左右子树。递归三部曲1:确认终止条件，当左指针大于右指针时，递归结束。2.确认传入参数，有序数组，左指针和右指针。3.确认单层递归逻辑:将当前left和right中的中间节点设置为根节点，满足条件就返回。
class Solution {
public:TreeNode* helper(vector<int>& nums, int left, int right){int mid=left+(right-left)/2;if(left>right){return nullptr;}TreeNode* root=new TreeNode(nums[mid]);root->left=helper(nums,left,mid-1);root->right=helper(nums,mid+1,right);return root;}
public:TreeNode* sortedArrayToBST(vector<int>& nums) {int left=0;int right=nums.size()-1;TreeNode* root=helper(nums,left,right);return root;}
};538.把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
思路: 累加树 由题意可知，在二叉搜索树中的递归顺序是右中左的顺序，创建一个新的函数，进行右中左的遍历，在遍历中要将节点的值记录下来，用来做累加
class Solution {
public:
int pre;void travleRoot(TreeNode* root){if(root==nullptr){return ;}travleRoot(root->right);root->val+=pre;pre=root->val;travleRoot(root->left);}
public:TreeNode* convertBST(TreeNode* root) {travleRoot(root);return root;}
};415.字符串相加:
给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
思路:双指针，定义两个指针指向两个字符串的尾部，然后将二者指向的字符转成整数相加，(在这里我用了三元组来进行数字字符与整数间的转换，就是将字符减去‘0’的ASCII值)
class Solution {
public:string addStrings(string num1, string num2) {//字符减去字符 '0' 的操作可以将字符表示的数字转换为对应的整数int i=num1.size()-1;int j=num2.size()-1;string aus;for(int c=0;i>=0||j>=0||c;--i,--j){ int a=i<0?0:num1[i]-'0';int b=j<0?0:num2[j]-'0';//字符 num1[i] 对应的数字字符转换为相应的整数值。c+=a+b;aus+=to_string(c%10);c/=10;}reverse(aus.begin(),aus.end());return aus;}
};669.修剪二叉搜索树
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
思路:最开始没有判断当当前节点小于最小值时，当前节点的右侧节点的情况，和当前节点大于最大值时，当前节点的左节点的情况，所以出错了，因此要在代码中判断一下这两种情况。
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root==nullptr){return nullptr;}if(root->val<low){TreeNode* right=trimBST(root->right,low,high);return right;}if(root->val>high){ TreeNode*left=trimBST(root->left,low,high);return left;}root->left=trimBST(root->left,low,high);root->right=trimBST(root->right,low,high);return root;}
};
