非科班学习算法day21 | LeetCode669:修剪二叉搜索树 ，Leetcode108:将有序数组转换为二叉搜索树 ，Leetcode538:把二叉搜索树转换为累加树
介绍
包含LC的两道题目，还有相应概念的补充。
相关图解和更多版本：
代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF
二、LeetCode题目
1.LeetCode669:修剪二叉搜索树
题目链接：669. 修剪二叉搜索树 - 力扣（LeetCode）
题目解析
这道题第二次做一开始还是迷糊，其实本质还是删除节点，只不过我们需要直到，不能看到没在范围的就直接删除，因为其子树也是有大有小的，所以就要处理相应的节点。那就是在下限之下，向右边遍历；在上限之上，向左边遍历。同时对于节点的拼接处理就是去掉一半子树。思路想清楚代码看起来还是比较简洁。
c++代码如下：
/**
* 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) return nullptr;
if(root->val<low)
{
return trimBST(root->right, low,high);
}
if(root->val >high)
{
return trimBST(root->left,low,high);
}
root->left = trimBST(root->left,low,high);
root->right = trimBST(root->right,low,high);
return root;
}
};2.Leetcode108:将有序数组转换为二叉搜索树
题目链接：108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
题目解析
一开始还在想是不是需要将奇偶分类，实际上没有必要，因为有平衡的要求也不用慌，因为最中间的两个值，用左边和右边构造是一样的。这里就采用中间左边构造的形式。
需要理清思路：每层选取最中间的数作为根节点，有点像之前根据遍历顺序构造数的做法。想清楚这个之后，代码才能好写起来。
C++代码如下：
/**
* 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* sorted(vector<int>& nums, int left, int right) {
if(left>right) return nullptr;
int mid = left + (right - left) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = sorted(nums, left, mid - 1);
root->right = sorted(nums, mid + 1, right);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return sorted(nums, 0, nums.size() - 1);
}
};注意点：因为要整个遍历，且返回值是作为对应根节点的孩子节点接住的！所以直接用root->left
3.Leetcode538:把二叉搜索树转换为累加树
题目链接：538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）
题目解析
一眼看上去也是构造树，不过这道题不需要动节点，只需要返回节点的值进行运算就可以，这里也是用回溯的思想。先遍历右边将右边的值返回，中做处理，就是相加，最后遍历左边。这样就符合了累加树的计算方法
C++代码如下：
/**
* 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 sum = 0;
TreeNode* convertBST(TreeNode* root) {
if (!root)
return nullptr;
convertBST(root->right);
sum += root->val;
root->val = sum;
convertBST(root->left);
return root;
}
};注意点1：只是提供了一种新的思路，面对二叉树要灵活，把已经做过的看看能不能用上。
总结
补打卡第21天，坚持！！！
