669. 修剪二叉搜索树
看到这道题，我的想法就是复刻前天的最后一题，因为同样都是删除二叉树节点。但是那道题我是看会了，自己写起来还是有点怵。这回参照着上次的，半看半理解的写了出来。但是发现有的时候不对呢。
class Solution {
public:
bool inbetween(TreeNode* cur, int low, int high){
if((cur->val<low) || (cur->val>high)){
return true;
}
else{
return false;
}
}
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(root == nullptr){
return root;
}
if(inbetween(root,low,high)){
if((root->left == nullptr) && (root->right == nullptr)){
delete root;
return nullptr;
}
else if((root->left != nullptr) && (root->right == nullptr)){
TreeNode* temp = root->left;
delete root;
return temp;
}
else if((root->left == nullptr) && (root->right != nullptr)){
TreeNode* temp = root->right;
delete root;
return temp;
}
else{
TreeNode* cur = root->right;
while(cur->left != nullptr){
cur = cur->left;
}
cur->left = root->left;
TreeNode* temp = root;
root = root->right;
delete root;
return root;
}
}
root->left = trimBST(root->left,low,high);
root->right = trimBST(root->right,low,high);
return root;
}
};
看了答案也不是很懂为什么不能像上一题那么做。
108.将有序数组转换为二叉搜索树
Yeah！这道题一遍成！稍微简单一点的递归还是不太难。(刚写完这句话看了一眼，原来是简单题。。。)
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if(nums.size() == 0){
return nullptr;
}
int mid = (nums.size()-1)/2;
TreeNode* cur = new TreeNode(nums[mid]);
vector<int> left_vec(nums.begin(),nums.begin()+mid);
vector<int> right_vec(nums.begin()+mid+1, nums.end());
cur->left = sortedArrayToBST(left_vec);
cur->right = sortedArrayToBST(right_vec);
return cur;
}
};
538.把二叉搜索树转换为累加树
这道题我看说应该用双指针，但是我直接粗暴的用了一个public变量来记录。一边也成了。
class Solution {
public:
TreeNode* pre;
int sum = 0;
TreeNode* convertBST(TreeNode* root) {
if(root == nullptr){
return root;
}
convertBST(root->right);
root->val = root->val + sum;
sum = root->val;
convertBST(root->left);
return root;
}
};
