算法打卡 Day25（二叉树）-修剪二叉搜索树 + 将有序数组转换为二叉搜索树 + 把二叉搜索树转换为累加树

Leetcode 669-修剪二叉搜索树

题目描述

https://leetcode.cn/problems/trim-a-binary-search-tree/description/

解题思路

对于每个节点，如果其值小于区间最小值，不能直接将其完全删除，而应判断其右子树的值（该节点值小于区间，但右子树的值大于该节点，可能属于区间范围内）；同理，如果节点值大于区间范围，则需要进一步判断该节点的左子树是否属于区间范围。

/*** 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 == nullptr) return nullptr;else if (root->val < low) return trimBST(root->right,low,high);else 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;}
};

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

题目描述

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/

解题思路

/*** 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* traversal(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 = traversal(nums,left, mid-1);root->right = traversal(nums,mid+1,right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return traversal(nums,0, nums.size()-1);}
};

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

题目描述

https://leetcode.cn/problems/convert-bst-to-greater-tree/description/

解题思路

根据二叉搜索树的性质可知，右侧节点大于根节点大于左侧节点，因此采用右中左的遍历顺序，通过 pre 和 cur 双指针对每个节点的值进行累加

/*** 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 pre = 0;TreeNode* convertBST(TreeNode* root) {if(root == nullptr) return nullptr;//终止条件root ->right = convertBST(root->right);root->val += pre;pre = root->val;root->left = convertBST(root->left);return root;}
};