wordpress用网站测速,小兔自助建站系统,附近做广告牌的店,网站后台管理密码忘记目录1、leetcode 701. 二叉搜索树中的插入操作1、题目2、递归法3、迭代法2、leetcode 450. 二叉搜索树中的插入操作1、题目2、思路递归法3、迭代法4、删除结点的两个方法以及注意点3、leetcode 669. 修剪二叉搜索树1、题目2、思考与递归3、迭代法4、leetcode 108. 将有序数组转…
目录1、leetcode 701. 二叉搜索树中的插入操作1、题目2、递归法3、迭代法2、leetcode 450. 二叉搜索树中的插入操作1、题目2、思路递归法3、迭代法4、删除结点的两个方法以及注意点3、leetcode 669. 修剪二叉搜索树1、题目2、思考与递归3、迭代法4、leetcode 108. 将有序数组转换为二叉搜索树1、题目2、递归思路1、leetcode 701. 二叉搜索树中的插入操作
1、题目 给定二叉搜索树BST的根节点和要插入树中的值将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证新值和原始二叉搜索树中的任意节点值都不同。 注意可能存在多种有效的插入方式只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果 。 2、递归法
递归返回值以及参数 返回值为空因为我们进行的是插入操作不需要知道插在哪儿。 参数当前结点cur以及需要插入的数值val 终止条件 如果当前指针为空返回 单层逻辑 首先按照val的大小遍历左右子树。 如果当前结点的值大于val且此结点没有左孩子则可以将val构造的结点作为其左孩子。 如果当前结点的值小于val且此结点没有右孩子则可以将val构造的结点作为其右孩子。 否则return 最后在大函数里面返回root就行了。
/*** 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:void traversal(TreeNode* cur,int val){if(cur NULL) return;if(cur-val val) traversal(cur-left,val);if(cur-val val) traversal(cur-right,val);if(cur-val val cur-left NULL){//cout插入左结点endl;TreeNode* ansnew TreeNode(val);cur-left ans;}if(cur-val val cur-right NULL){//cout插入右结点endl;TreeNode* ansnew TreeNode(val);cur-right ans;}return;}TreeNode* insertIntoBST(TreeNode* root, int val) {if(root NULL){TreeNode* ansnew TreeNode(val);return ans;} traversal(root,val);return root;}
};进行了一些修改后的代码
/*** 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:void traversal(TreeNode* cur,int val){if(cur NULL) return;coutcur-valendl;if(cur-val val){traversal(cur-left,val);if(cur-left NULL){//cout插入左结点endl;TreeNode* ansnew TreeNode(val);cur-left ans;}} if(cur-val val){traversal(cur-right,val);if(cur-right NULL){//cout插入右结点endl;TreeNode* ansnew TreeNode(val);cur-right ans;}} return;}TreeNode* insertIntoBST(TreeNode* root, int val) {if(root NULL){TreeNode* ansnew TreeNode(val);return ans;} traversal(root,val);return root;}
};3、迭代法
在迭代法遍历的过程中需要记录一下当前遍历的结点的父结点这样才能进行插入结点操作。
/*** 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* insertIntoBST(TreeNode* root, int val) {if(root NULL){TreeNode* ansnew TreeNode(val);return ans;} TreeNode* cur root;TreeNode* parent root;//记录上一个结点否则不挖赋值新结点while(cur ! NULL){parent cur;if(cur-val val) cur cur-left;else cur cur-right;}TreeNode* node new TreeNode(val);if(val parent-val) parent-left node; //利用parent的结点的值进行赋值else parent-right node;return root;}
};2、leetcode 450. 二叉搜索树中的插入操作
1、题目
给定一个二叉搜索树的根节点 root 和一个值 key删除二叉搜索树中的 key 对应的节点并保证二叉搜索树的性质不变。返回二叉搜索树有可能被更新的根节点的引用。 一般来说删除节点可分为两个步骤 首先找到需要删除的节点 如果找到了删除它。 说明 要求算法时间复杂度为 O(h)h 为树的高度。
2、思路递归法
确定递归返回值和参数 通过递归返回值来删除结点。
TreeNode* deleteNode(TreeNode* root, int key)确定终止条件 遇到空结点返回说明了没有找到删除的结点。
if(root NULL) return root;确定单层逻辑 1、没有找到删除的结点遍历到空结点直接返回。 2、找到了删除的结点 【1】如果左右孩子都为空直接删除这个结点返回NULL为根结点 【2】如果左孩子为空右孩子不为空删除结点右孩子补位返回右孩子作为根结点 【3】如果右孩子为空左孩子不为空删除结点左孩子补位返回左孩子作为根结点 【4】如果左右孩子不为空则将删除结点的左子树的头结点放到删除结点的右子树的最左边结点的左孩子上返回删除结点右孩子作为新的结点 代表的是中序遍历序列的下一个节点。即比当前节点大的最小节点 if(root-val val){if(!root-left !root-right) return root;else if(!root-left root-right) return root-right;else if(root-left !root-right) return root-left;else {TreeNode* cur root-right;//找到右子树的最左边结点while(cur-left){cur cur-left;}cur-left root-left;TreeNode* tmp root-left;root root-right;delete tmp;return root;}}将新的结点返回给上一层上一层将其作为左或者右孩子
if(root-val key) root-left deleteNode(root-left,key);
if(root-val key) root-right deleteNode(root-right,key);/*** 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* deleteNode(TreeNode* root, int key) {if(root NULL) return root;if(root-val key){if(!root-left !root-right) return NULL; //直接删除结点返回NULLelse if(!root-left root-right) return root-right;else if(root-left !root-right) return root-left;else {TreeNode* cur root-right;//找到右子树的最左边结点while(cur-left){cur cur-left;}cur-left root-left;TreeNode* tmp root;root root-right;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;}
};3、迭代法
/*** 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* deleteOneNode(TreeNode* target){if(target NULL) return NULL;if(target-right NULL) return target-left;//如果right不为空,将left转移到right左子树的最左值。TreeNode* cur target-right;while(cur-left) cur cur-left;cur-left target-left;//返回target的右子树这样target结点就被删除了return target-right;}TreeNode* deleteNode(TreeNode* root, int key) {if(root NULL) return NULL;TreeNode* cur root;TreeNode* pre NULL; //记录cur的父结点用来删除cur//找到目标结点while(cur){if(cur-val key) break;pre cur;if(cur-val key) cur cur-left;else cur cur-right;}if(pre NULL) return deleteOneNode(cur); //如果搜索树只有头结点//删除右孩子还是删除左孩子,cur是父结点的左孩子还是右孩子if(pre-left pre-left-val key) pre-left deleteOneNode(cur);if(pre-right pre-right-val key) pre-right deleteOneNode(cur);return root;}
};4、删除结点的两个方法以及注意点
1、移动树找到目标结点直接对指针指向进行改变就结束了 2、覆盖值找到目标结点先将目标结点的值和目标结点的右子树的最左边的值进行交换交换后继续去递归遍历树直到再次遍历到目标结点的值此时目标结点已经是叶子结点左右孩子都为NULL直接就返回NULL指针实现了删除操作。先覆盖值后删除 3、删除一个结点不能简单地置这个结点为空我们需要修改父结点对此结点的指向 例如我们需要将root-right覆盖掉root不能root root-right;而是应该这样写; parent是root的父结点child可能是左孩子也可能是右孩子需要按照情况指定。
parent-child root-right; 3、leetcode 669. 修剪二叉搜索树
1、题目
给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构即如果没有被移除原有的父代子代关系都应当保留。 可以证明存在唯一的答案。 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。
2、思考与递归
因为是要遍历整棵树并且做修改其实不需要返回值也可以我们也可以完成修剪。但有返回值更方便可以通过递归函数的返回值来移除结点 如果当前结点的值小于low要对该结点的右孩子进行再次搜索直到找到满足区间的结点或者空结点最后返回right结点 如果当前结点的值大于high要对该结点的左孩子进行再次搜索直到找到满足区间的结点或者空结点最后返回left结点。 自上而下遍历检查直到整棵树遍历完。 依次遍历结点左右孩子并将返回的结果作为当前结点的左右孩子。 最后返回当前结点。 返回的结点必然是val在区间内或者是空结点。 /*** 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 NULL) return root;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-left trimBST(root-left,low,high);用结点3的左孩子把下一层返回的结点0的右孩子(结点2)接住。此时结点3的右孩子就变成了结点2将结点0从二叉树中移除了。
错误思路记录先得到中序遍历的结果然后修剪结果数组然后通过修剪后的数组构造一个二叉搜索树.但是这个思路是错误的因为单纯用一个中序遍历数组不能构造出唯一的二叉树随意选择一种方法会改变二叉树的结构 如low1,high3,预期结果应为 但是我们这样做的结果是
3、迭代法
剪枝的三个步骤: 1、将root移动到[L,R]范围内 2、剪枝左子树 3、剪枝右子树 个人认为这个思路比较好理解一点虽然繁琐了些。
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root NULL) return root;//1、处理头结点让root移动到[L,R]范围内while(root-val low || root-val high){if(root-val low) root root-right; //小于L往右走else root root-left; //大于R的往左走}TreeNode* cur root;//此时root已经在[L,R]范围内了处理左孩子元素小于L的情况while(cur){//如果左孩子比low小就用左孩子的右孩子替代左孩子while(cur-left cur-left-val low){cur-left cur-left-right;}//一直遍历左孩子cur cur-left;}cur root;//此时root已经在范围内处理右孩子元素大于R的情况while(cur){//如果右孩子比high大就用右孩子的左孩子替代右孩子while(cur-right cur-right-val high){cur-right cur-right-left;}//一直遍历右孩子cur cur-right;}return root;}
};4、leetcode 108. 将有序数组转换为二叉搜索树
1、题目
将一个按照升序排列的有序数组转换为一棵高度平衡二叉搜索树。 本题中一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 利用数组构造二叉树的本质就是寻找分割点分割点作为当前结点然后递归左区间和右区间。 有序数组的分割点我们选择数组中间位置的结点。 如果数组长度为偶数中间结点有两个两者取其一都可以所以也就造成了答案不是唯一的。
2、递归思路
递归返回值以及参数 返回值为结点,我们要用返回值来构造中结点的左右孩子。 参数数组分割数组的左边界、分割数组的右边界这里我们定义区间是左闭右闭的。
TreeNode* traversal(vectorint nums,int left,int right)终止条件 由于区间的定义为左闭右闭所以当leftright时就是空结点了。
if(left right) return nullptr;确定单层逻辑 1、取中间值int mid left ((right - left) / 2);这个是取靠左的中间值这样可以防止right\left过大时导致的数值越界。 2、以中间位置的元素构造结点 TreeNode* root new TreeNode(nums[mid]); 3、划分区间。root-left接住下一层左区间的构造结点root-right接住下一层的右区间构造的结点。
int mid left ((right - left) / 2);
TreeNode* root new TreeNode(nums[mid]);
root-left traversal(nums,left,mid-1);
root-right traversal(nums,mid1,right);对于数组[-10,-3,0,5,9]观察遍历过程 区间0,4 中间结点0 区间0,1 中间结点-10 区间0,-1 中间结点NULL 区间1,1 中间结点-3 区间1,0 中间结点NULL 区间2,1 中间结点NULL 区间3,4 中间结点5 区间3,2 中间结点NULL 区间4,4 中间结点9 区间4,3 中间结点NULL 区间5,4 中间结点NULL /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* traversal(vectorint nums,int left,int right){cout区间left,rightendl;if(left right){cout中间结点NULLendl;return nullptr;}int mid left ((right - left) / 2);cout中间结点nums[mid]endl;TreeNode* root new TreeNode(nums[mid]);root-left traversal(nums,left,mid-1);root-right traversal(nums,mid1,right);return root;}TreeNode* sortedArrayToBST(vectorint nums) {TreeNode* root traversal(nums,0,nums.size()-1);return root;}
};
