代码随想录算法训练营第二十一天| 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树

一、LeetCode 669. 修剪二叉搜索树

题目链接：LeetCode 669. 修剪二叉搜索树述

文章讲解：代码随想录
视频讲解：你修剪的方式不对，我来给你纠正一下！| LeetCode：669. 修剪二叉搜索树

思路：

题目确定了一个区间[low, high]，要求调整二叉搜索树使得所有节点值都在这个范围内；我们首先可以观察一下二叉搜索树的结构，为左子树所有结点小于当前结点，右子树所有结点大于当前结点。因此在遍历到一个结点值在区间之外时（若小于），该结点和该结点的左子树所有结点都不符合条件，可以直接删除，而右子树包含大于该结点的值，有可能含有在区间内的结点，因此进入右子树继续遍历。
在这里插入图片描述
对于递归函数的设计，仍然按照递归三部曲进行设计；

确定函数传参与返回值：可以直接采用题目给出的函数模板作为递归函数的传参与返回值

TreeNode* trimBST(TreeNode* root, int low, int high)

确定递归边界条件：由于返回值格式为TreeNode*，因此在遍历到空节点时返回空指针NULL.

if(!root) return NULL;

确定递归函数逻辑：按照我们上面分析的内容设计算法，当前结点值满足条件时，左右孩子分别是下一层递归的返回值；若当前结点值小于区间左边界，那么本结点与本结点的左子树全部舍弃，将右孩子传入下一层递归，并将递归的返回值设置为新的结点；节点值大于区间右边界的处理类似。

if(root->val >= low && root->val <= high){root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);}else{if(root->val < low){root = trimBST(root->right, low, high);}else if(root->val > high){root = trimBST(root->left, low, high);}}

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 NULL;if(root->val >= low && root->val <= high){root->left = trimBST(root->left, low, high);root->right = trimBST(root->right, low, high);}else{if(root->val < low){root = trimBST(root->right, low, high);}else if(root->val > high){root = trimBST(root->left, low, high);}}return root;}
};

二、LeetCode 108.将有序数组转换为二叉搜索树

题目链接：LeetCode 108.将有序数组转换为二叉搜索树

文章讲解：代码随想录
视频讲解：构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树

思路

题目要求将升序数组转化为平衡二叉搜索树，即树中任意结点的左右子树深度差不大于2；我们可以使用与之前类似的分割数组分别传入下一层的方法，进行递归设计。

要求构建平衡二叉树，我们可以每次都将数组以中位数为分界点，平分成左右两部分，此时两部分基本长度相同，长度差不超过1，意味着结点的左右子树深度差不超过1，达到了题目要求的平衡要求。

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* sortedArrayToBST(vector<int>& nums) {if(nums.empty()) return NULL;auto median = nums.begin() + (nums.end()-nums.begin())/2;TreeNode* root = new TreeNode(*median);if(nums.size() != 1){vector<int> nums_left(nums.begin(), median);vector<int> nums_right(median + 1, nums.end());root->left = sortedArrayToBST(nums_left);root->right = sortedArrayToBST(nums_right);}return root;}
};

三、LeetCode 538.把二叉搜索树转换为累加树

题目链接：LeetCode 538.把二叉搜索树转换为累加树

文章讲解：代码随想录
视频讲解：普大喜奔！二叉树章节已全部更完啦！| LeetCode：538.把二叉搜索树转换为累加树

思路

反中序遍历

将二叉搜索树转化为累加树，即把二叉树中所有大于等于该结点值的和，设定为当前结点的新值，那么就需要找二叉树中大于等于当前结点的值，而二叉树的中序遍历的逆序恰好符合从大到小的顺序，因此设置一个反中序递归的函数进行累加赋值即可。
在这里插入图片描述
设置一个全局变量，记录前一个结点的值，加上本节点的值进行赋值，从而实现累加；可写出如下代码：

class Solution {
private:int pre = 0; // 记录前一个节点的数值void traversal(TreeNode* cur) { // 右中左遍历if (cur == NULL) return;traversal(cur->right);cur->val += pre;pre = cur->val;traversal(cur->left);}
public:TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};

变量传参递归（野路子）

由于笔者初次看到本题时，理解题目有一些偏差，在算法设计上有些过于复杂了，但简化后的代码底层思想与反中序遍历还是相似的。

笔者首先设置了一个整数参数parVal加入递归传参，类似于反中序遍历中的前一个结点值，记录了比自己结点大的所有结点值之和。笔者对于本题的结点处理，只有当当前结点为左叶子结点时，才加上parVal（否则这一条分支上会重复加上parVal），其余情况都加上自己的孩子结点的返回值；对于结点处理，分出了两个方面的八种情况，即：

该结点是它的双亲的左/右孩子（2种）
该结点的孩子结点情况：有两个孩子、只有左孩子、只有右孩子、无孩子结点

在列出八中情况的结点处理和递归返回值后，经过归纳简化可化简出如下结果：**如果该结点有右孩子，则它的新值是他原本的值加上自己右孩子的下一层递归返回值（相当于返回前一个结点值），否则需要加上parVal（见上面的结点处理规定）；如果结点有左孩子，那么递归的返回值是当前结点的左孩子的下一层递归返回值（左子树只返回最左下方的最大值），否则返回当前结点值。**按照这样的规律调整出的代码如下：

/*** 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 convertBST(TreeNode* root, int parVal){if(!root) return 0;          if(root->right){root->val += convertBST(root->right, parVal); //此时函数返回相当于前一个结点值}else{root->val += parVal;}if(root->left) return convertBST(root->left, root->val);else return root->val;}TreeNode* convertBST(TreeNode* root) {int val = convertBST(root, 0);return root;}
};