669. 修剪二叉搜索树
思路：
因为是二叉搜索树，所以如果中间的节点小于区间的最小值，还需要判断中间节点的右子树是否满足区间要求，同理，如果中间的节点大于区间的最大值，则还需要判断中间节点的左子树是否满足区间要求。
代码：
/**
* 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:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(root==NULL) return NULL;
if(root->val<low)
{
TreeNode* righttree=trimBST(root->right,low,high);
return righttree;
}
if(root->val>high)
{
TreeNode* lefttree=trimBST(root->left,low,high);
return lefttree;
}
root->left=trimBST(root->left,low,high);
root->right=trimBST(root->right,low,high);
return root;
}
};
108. 将有序数组转换为二叉搜索树
思路：
先找到数组的中间节点作为根节点，这样就能保证左右两边构造的深度差不会超过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 {
public:
TreeNode* sorttree(vector<int>& nums,int low,int high)
{
if(low>high) return NULL;
int mid=(high+low)/2;
TreeNode* root=new TreeNode(nums[mid]);
root->left=sorttree(nums,low,mid-1);
root->right=sorttree(nums,mid+1,high);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return sorttree(nums,0,nums.size()-1);
}
};
538. 把二叉搜索树转换为累加树
思路：
题意是对于数值小的节点，要把比这个数值大的节点全部加在一起，以此类推。根据二叉搜索树的特点，应该是先采用右中左的顺序遍历并累加即可。
代码：
/**
* 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 pre=0;
void convert(TreeNode* cur)
{
if(cur==NULL)return ;
convert(cur->right);
cur->val+=pre;
pre=cur->val;
convert(cur->left);
return;
}
TreeNode* convertBST(TreeNode* root) {
pre=0;
convert(root);
return root;
}
};
