外贸最大电子元器件交易网站,百度域名登录,广州seo代理商,5 电子商务网站建设的步骤1.二叉搜索树中的插入操作#xff08;701题#xff09;
题目描述#xff1a;给定二叉搜索树#xff08;BST#xff09;的根节点和要插入树中的值#xff0c;将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证#xff0c;新值和原始二叉搜索树中的任意…1.二叉搜索树中的插入操作701题
题目描述给定二叉搜索树BST的根节点和要插入树中的值将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据保证新值和原始二叉搜索树中的任意节点值都不同。 递归法 只要遍历二叉搜索树找到空节点 插入元素就可以了有返回值的话可以利用返回值完成新加入的节点与其父节点的赋值操作
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {//节点为空节点就是需要插入节点位置并且把插入的节点返回if(root NULL){TreeNode* node new TreeNode(val);//新创建一个节点return node;//把这个节点返回}if(root-val val)root-left insertIntoBST(root-left,val);//根节点值大于目标值左根节点小于目标值右if(root-val val)root-right insertIntoBST(root-right,val);return root;}
};
迭代法使用了pre和cur两个指针的方法来实现迭代
class Solution {
public://双指针的想法来实现前一个节点和后一个节点来同时移动TreeNode* insertIntoBST(TreeNode* root, int val) {if(root NULL){TreeNode* node new TreeNode(val);return node;}TreeNode* pre root;//记录上一个节点对新的节点赋值操作TreeNode* cur root;while(cur ! NULL){pre cur;if(cur-val val)cur cur-left;else cur cur-right;}TreeNode* node new TreeNode(val);if(val pre-val) pre-left node;//使用pre节点对其赋值else pre-right node;return root;}
};
2.删除二叉搜索树中的节点450题
题目描述
给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变。返回二叉搜索树有可能被更新的根节点的引用。
一般来说删除节点可分为两个步骤
首先找到需要删除的节点 如果找到了删除它。 说明 要求算法时间复杂度为 $O(h)$h 为树的高度。 递归法需要考虑好根节点情况判断要删除节点左右孩子情况
第一种情况没找到删除的节点遍历到空节点直接返回了找到删除的节点 第二种情况左右孩子都为空叶子节点直接删除节点 返回NULL为根节点第三种情况删除节点的左孩子为空右孩子不为空删除节点右孩子补位返回右孩子为根节点第四种情况删除节点的右孩子为空左孩子不为空删除节点左孩子补位返回左孩子为根节点第五种情况左右孩子节点都不为空则将删除节点的左子树头结点左孩子放到删除节点的右子树的最左面节点的左孩子上返回删除节点右孩子为新的根节点。
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if(root nullptr)return root;//没找到删除的节点遇到空节点直接返回//根节点的值等于目标值if(root-val key){if(root-left nullptr)return root-right;//左孩子为空返回右节点else if(root-right nullptr)return root-left;//右孩子为空返回左节点else{TreeNode* cur root-right;//查找右子树上的最左面的节点//找最左面的节点while(cur-left!nullptr){cur cur-left;}cur-left root-left;//删除的节点左子树放在cur左子树上TreeNode* tmp root;//保存root节点root root-right;//返回右孩子作新的root节点delete tmp;//删除节点return root;}} if(root-val key)root-left deleteNode(root-left,key);//左if(root-val key)root-right deleteNode(root-right,key);//右return root;}
};
普通二叉树的递归方式
代码中目标节点要删除的节点被操作了两次
第一次是和目标节点的右子树最左面节点交换。第二次直接被NULL覆盖了。
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root nullptr) return root;if (root-val key) {if (root-right nullptr) { // 这里第二次操作目标值最终删除的作用return root-left;}TreeNode *cur root-right;while (cur-left) {cur cur-left;}swap(root-val, cur-val); // 这里第一次操作目标值交换目标值其右子树最左面节点。}root-left deleteNode(root-left, key);root-right deleteNode(root-right, key);return root;}
};
迭代法
class Solution {
private:TreeNode* deleteNodeOperation(TreeNode* target){if(target nullptr)return target;if(target-right nullptr)return target-left;TreeNode* cur target-right;while(cur-left){cur cur-left;}cur-left target-left;return target-right;}
public:TreeNode* deleteNode(TreeNode* root, int key) {if(root nullptr)return root;TreeNode* cur root;TreeNode* pre nullptr;while(cur){if(cur-val key)break;pre cur;if(cur-val key)cur cur-left;else cur cur-right;}if(pre nullptr){return deleteNodeOperation(cur);}if(pre-left pre-left-val key){pre-left deleteNodeOperation(cur);}if(pre-right pre-right-val key){pre-right deleteNodeOperation(cur);}return root;}
};
因为二叉搜索树添加节点只需要在叶子上添加就可以的不涉及到结构的调整而删除节点操作涉及到结构的调整。主要难点在于如何处理左右节点都不为空情况
3.修剪二叉搜索树 669题
题目描述
给定一个二叉搜索树同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树使得所有节点的值在[L, R]中 (RL) 。你可能需要改变树的根节点所以结果应当返回修剪好的二叉搜索树的新的根节点。 递归法那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了就是把节点0从二叉树中移除 上一个节点接收下面返回值直接返回
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root nullptr)return nullptr;//空节点返回if(root-val low){TreeNode* right trimBST(root-right,low,high);//寻找在区间内的节点return right;}if(root-val high){TreeNode* left trimBST(root-left,low,high);//寻找区间内的节点return left;}root-left trimBST(root-left,low,high);//左root-right trimBST(root-right,low,high);//右return root;}
}; 迭代法二叉搜索树有序不用栈去辅助就可实现
在剪枝的时候可以分为三步
将root移动到[L, R] 范围内注意是左闭右闭区间剪枝左子树剪枝右子树
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;}
};
4.将有序数组转换为二叉搜索树108题
将一个按照升序排列的有序数组转换为一棵高度平衡二叉搜索树。
本题中一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 递归法 用数组的下标来操作数组递归时候遵循循环不变量原则
class Solution {
private:TreeNode* traversal(vectorint 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;}
public:TreeNode* sortedArrayToBST(vectorint nums) {TreeNode* root traversal(nums,0,nums.size()-1);//调用递归return root;}
};
迭代法使用三个队列实现一个队列放遍历的节点一个队列放左区间下标一个队列放右区间下标。
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;}
};
5.把二叉搜索树转换为累加树538题
题目描述
给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下二叉搜索树满足下列约束条件
节点的左子树仅包含键 小于 节点键的节点。 节点的右子树仅包含键 大于 节点键的节点。 左右子树也必须是二叉搜索树。 递归法从树中可以看出累加的顺序是右中左所以我们需要反中序遍历这个二叉树然后顺序累加就可以了
一个pre指针记录当前遍历节点cur的前一个节点
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;}
};
总结
二叉搜索树的插入操作此题需要做的就是找到叶子节点然后再根据二叉搜索树的特性来然后去接收左子树和右子树向上返回再根据二叉搜索树的特性来完成实现根据值来遍历迭代法使用两个节点的方法来实现
删除二叉搜索树中的节点这里要考虑递归法的终止条件设定考虑好左右子树是否为空的几种情况再对这些情况做出相应的处理主要注意左右子树不为空的情况如何去处理需要在右子树的最左子树的节点去将左子树接收然后把值去掉接收右子树即可迭代法去实现
修剪二叉搜索树利用了删除二叉搜索树的方法来实现就是需要将减枝下来的节点去接收然后再进行迭代注意二叉搜索树是根据值来递归的因为其值有大小有序所以可以按照这个方向来进行递归
将有序数组转换成二叉搜索树将一个数组按照中间数据进行分割然后再进行左数组和右数组进行分别来进行递归按照取中间节点操作进行然后按照节点值来进行递归最好按照数组的下标来进行操作就好了
把二叉搜索树转换为累加树累加树来进行数值的反中序遍历先进行右遍历然后处理中间节点的操作之后再进行左处理注需要使用整形的数来接收前一个节点的值来实现其实和双指针的想法差不多
