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

本文主要是介绍小山菌_代码随想录算法训练营第二十三天| 669. 修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

669. 修剪二叉搜索树

文档讲解：代码随想录.修剪二叉搜索树
视频讲解：你修剪的方式不对，我来给你纠正一下！| LeetCode：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* sortedArrayToBST(vector<int>& nums) {return helper(nums, 0, nums.size() - 1); // 数组，左侧索引和右侧索引}// 二叉搜索树的中序遍历是升序序列，题目给定的数组是按照升序排序的有序数组，TreeNode* helper(vector<int>& nums, int left, int right) {if (left > right) {return nullptr;}// 总是选择中间位置左边的数字作为根节点int mid = (left + right) / 2;TreeNode* root = new TreeNode(nums[mid]);root->left = helper(nums, left, mid - 1);root->right = helper(nums, mid + 1, right);return root;}
};

心得体会

1.一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1

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

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

代码实现

/*** 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) {return helper(nums, 0, nums.size() - 1); // 数组，左侧索引和右侧索引}// 二叉搜索树的中序遍历是升序序列，题目给定的数组是按照升序排序的有序数组，TreeNode* helper(vector<int>& nums, int left, int right) {if (left > right) {return nullptr;}// 总是选择中间位置左边的数字作为根节点int mid = (left + right) / 2;TreeNode* root = new TreeNode(nums[mid]);root->left = helper(nums, left, mid - 1);root->right = helper(nums, mid + 1, right);return root;}
};

心得体会

1.一个高度平衡二叉树是指一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1

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

文档讲解：代码随想录.把二叉搜索树转换为累加树
视频讲解：普大喜奔！二叉树章节已全部更完啦！| LeetCode：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 {private:int pre = 0;void travesral(TreeNode* root) {if (root == nullptr) {return;}travesral(root->right);root->val += pre;pre = root->val;travesral(root->left);}public:TreeNode* convertBST(TreeNode* root) {pre = 0;travesral(root);return root;}
};