重庆忠县网站建设公司哪家专业,三合一网站建设用途,网站如何引导页,浙江建设监理协会官方网站代码随想录二刷Day23
今日任务
669.修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树 语言#xff1a;C
669. 修剪二叉搜索树
链接#xff1a;https://leetcode.cn/problems/trim-a-binary-search-tree/ 递归
class Solution {
public:Tree…代码随想录二刷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(vectorint 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(vectorint nums) {if(nums.size() 1) return new TreeNode(nums[0]);return traversal(nums, 0, nums.size() - 1);}
};迭代
class Solution {
public:TreeNode* sortedArrayToBST(vectorint nums) {queueTreeNode* nodeQue;queueint leftQue;queueint 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;stackTreeNode* 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;}
};
