代码随想录打卡第23天 669. 修剪二叉搜索树 108. 将有序数组转换为二叉搜索树 538. 把二叉搜索树转换为累加树
669. 修剪二叉搜索树
题目链接：https://leetcode.cn/problems/trim-a-binary-search-tree/
算法思想：
二叉树的终止条件：
遇到比low小或者比high大的元素，开始处理。
如果遇到比low小的元素，那就递归处理它的右孩子，并且用left接住这个递归返回的节点，返回给上一层。
如果遇到比high大的元素，那就递归处理它的左孩子，并且用right接住这个递归返回的节点，返回给上一层。
代码：
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
//
if(root==NULL)
return root;
if(root->val < low)
{
//找到比low小的根节点了,去看下右孩子需要保留的地方
TreeNode* left = trimBST(root->right, low, high);
return left;
}
if(root->val > high)
{
TreeNode* right = trimBST(root->left, low, high);
return right;
}
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
};
108. 将有序数组转换为二叉搜索树
题目链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
算法思想：相当于是进行二分查找，均匀的把数组分成平衡的两个部分，递归构造左右孩子。
注意区间的定义是左闭右开还是左闭右闭。
代码：
class Solution {
public:
TreeNode* buildtree(vector<int>& nums, int start, int end)
{
if(start>=end)
return NULL;
int mid = (start+end)/2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = buildtree(nums, start, mid);
root->right = buildtree(nums, mid+1, end);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
//可以采用二分法对树进行构建
TreeNode* root = buildtree(nums, 0, nums.size());
return root;
}
};
538. 把二叉搜索树转换为累加树
题目链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/
算法思想：
可以想到，用二叉搜索树中序遍历是将从小到大遍历。我们现在需要从大到小遍历，就采用右中左的方式遍历，并用一个全局变量sum记录累加的数值进行更新。
代码：
class Solution {
public:
int sum=0;
void countval(TreeNode* root)
{
if(root==NULL)
return;
countval(root->right);
sum = sum+root->val;
root->val = sum;
countval(root->left);
}
TreeNode* convertBST(TreeNode* root) {
countval(root);
return root;
}
};
