代码随想录二刷Day23

今日任务

669.修剪二叉搜索树
108.将有序数组转换为二叉搜索树
538.把二叉搜索树转换为累加树
语言：C++

669. 修剪二叉搜索树

链接：https://leetcode.cn/problems/trim-a-binary-search-tree/
递归

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == NULL) return NULL;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;}
};

迭代

class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root == NULL) return NULL;while(root && (root->val < low || root->val > high)){if(root->val < low) root = root->right; //左边没必要修建了，都不符合条件else root = root->left;}//当前root的值肯定是位于[low,high]中的TreeNode* cur = root;while(cur){//左侧的值是更小的，直接剪掉while(cur->left && cur->left->val < low){cur->left = cur->left->right;}cur = cur->left;}cur = root;while(cur){//右侧的值是更大的，直接剪掉while(cur->right && cur->right->val > high){cur->right = cur->right->left;}cur = cur->right;}return root;}
};

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

链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
递归

class Solution {
public:TreeNode* traversal(vector<int>& nums, int left, int right){if(left > right) return NULL;if(left == right) return new TreeNode(nums[left]);int mid = left + ((right - left) >> 1);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) {if(nums.size() == 1) return new TreeNode(nums[0]);return traversal(nums, 0, nums.size() - 1);}
};

迭代

class Solution {
public:TreeNode* sortedArrayToBST(vector<int>& nums) {queue<TreeNode*> nodeQue;queue<int> leftQue;queue<int> rightQue;TreeNode* root = new TreeNode(0);nodeQue.push(root);leftQue.push(0);rightQue.push(nums.size() - 1);while(!nodeQue.empty()){int left = leftQue.front(); leftQue.pop();int right = rightQue.front(); rightQue.pop();int mid = left + ((right - left) >> 1);TreeNode* cur = nodeQue.front(); nodeQue.pop();cur->val = nums[mid];if(left <= mid - 1){cur->left = new TreeNode(0);nodeQue.push(cur->left);leftQue.push(left);rightQue.push(mid - 1);}if(mid + 1 <= right){cur->right = new TreeNode(0);nodeQue.push(cur->right);leftQue.push(mid + 1);rightQue.push(right);}}return root;}
};

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

链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/
递归

class Solution {
public:int sum = 0;int curSum = 0;void getSum(TreeNode* root){if(root == NULL) return;getSum(root->left);sum += root->val;getSum(root->right);}void traversal(TreeNode* root){if(root == NULL) return;traversal(root->left);int tmp = root->val;root->val = sum - curSum;curSum += tmp;traversal(root->right); }TreeNode* convertBST(TreeNode* root) {if(root == NULL) return root;getSum(root);traversal(root);return root;}
};

没有必要中序遍历，按照右中左遍历即可

class Solution {
public:int pre = 0;void traversal(TreeNode* root){if(root == NULL) return;traversal(root->right);root->val += pre;pre = root->val;traversal(root->left);}TreeNode* convertBST(TreeNode* root) {traversal(root);return root;}
};

迭代

class Solution {
public:TreeNode* convertBST(TreeNode* root) {if(root == NULL) return root;int pre = 0;stack<TreeNode*> st;TreeNode* cur = root;//中序遍历反过来 while(!st.empty() || cur){if(cur){st.push(cur); //rootcur = cur->right;}else{cur = st.top();st.pop();cur->val += pre;pre = cur->val;cur = cur->left;}}return root;}
};