建立网站原理,网站备案时间要多久,制作公众号,深圳免费推广网站大全669 修剪二叉搜索树
给定一个二叉搜索树#xff0c;同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树#xff0c;使得所有节点的值在[L, R]中 (RL) 。你可能需要改变树的根节点#xff0c;所以结果应当返回修剪好的二叉搜索树的新的根节点。
class Solution {
pub…669 修剪二叉搜索树
给定一个二叉搜索树同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树使得所有节点的值在[L, R]中 (RL) 。你可能需要改变树的根节点所以结果应当返回修剪好的二叉搜索树的新的根节点。
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root nullptr) return root; //如果是空节点直接返回//如果结点小于最小结点这个肯定要删此时看一下右孩子们小不小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 L, int R) {if (!root) return nullptr;// 处理头结点让root移动到[L, R] 范围内注意是左闭右闭while (root ! nullptr (root-val L || root-val R)) {if (root-val L) root root-right; // 小于L往右走else root root-left; // 大于R往左走}TreeNode *cur root;// 此时root已经在[L, R] 范围内处理左孩子元素小于L的情况while (cur ! nullptr) {while (cur-left cur-left-val L) {cur-left cur-left-right;}cur cur-left;}cur root;// 此时root已经在[L, R] 范围内处理右孩子大于R的情况while (cur ! nullptr) {while (cur-right cur-right-val R) {cur-right cur-right-left;}cur cur-right;}return root;}
};
108.将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组转换为一棵高度平衡二叉搜索树。
本题中一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
class Solution {
private:TreeNode* traversal(vectorint nums, int left, int right) {if(right left) return nullptr;//为了保证平衡新创建的一定是中间头结点int middle (leftright)/2;TreeNode* root new TreeNode(nums[middle]);root-left traversal(nums,left,middle-1);root-right traversal(nums, middle1,right);return root;}
public:TreeNode* sortedArrayToBST(vectorint nums) {return traversal(nums,0,nums.size()-1);}
};
迭代法比较复杂这里先记录一下
class Solution {
public:TreeNode* sortedArrayToBST(vectorint nums) {if (nums.size() 0) return nullptr;TreeNode* root new TreeNode(0); // 初始根节点queueTreeNode* nodeQue; // 放遍历的节点queueint leftQue; // 保存左区间下标queueint rightQue; // 保存右区间下标nodeQue.push(root); // 根节点入队列leftQue.push(0); // 0为左区间下标初始位置rightQue.push(nums.size() - 1); // nums.size() - 1为右区间下标初始位置while (!nodeQue.empty()) {TreeNode* curNode nodeQue.front();nodeQue.pop();int left leftQue.front(); leftQue.pop();int right rightQue.front(); rightQue.pop();int mid left ((right - left) / 2);curNode-val nums[mid]; // 将mid对应的元素给中间节点if (left mid - 1) { // 处理左区间curNode-left new TreeNode(0);nodeQue.push(curNode-left);leftQue.push(left);rightQue.push(mid - 1);}if (right mid 1) { // 处理右区间curNode-right new TreeNode(0);nodeQue.push(curNode-right);leftQue.push(mid 1);rightQue.push(right);}}return root;}
}; 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;}
};
class Solution {
private:int pre; // 记录前一个节点的数值void traversal(TreeNode* root) {stackTreeNode* st;TreeNode* cur root;while (cur ! NULL || !st.empty()) {if (cur ! NULL) {st.push(cur);cur cur-right; // 右} else {cur st.top(); // 中st.pop();cur-val pre;pre cur-val;cur cur-left; // 左}}}
public:TreeNode* convertBST(TreeNode* root) {pre 0;traversal(root);return root;}
}; 二叉树就此完结
