一个网站内容怎么规划,企业网站建设感想,网站制作成功案例,找网络公司做网站需要注意什么C第二阶段——数据结构和算法#xff0c;之前学过一点点数据结构#xff0c;当时是基于Python来学习的#xff0c;现在基于C查漏补缺#xff0c;尤其是树的部分。这一部分计划一个月#xff0c;主要利用代码随想录来学习#xff0c;刷题使用力扣网站#xff0c;不定时更… C第二阶段——数据结构和算法之前学过一点点数据结构当时是基于Python来学习的现在基于C查漏补缺尤其是树的部分。这一部分计划一个月主要利用代码随想录来学习刷题使用力扣网站不定时更新欢迎关注 文章目录 一、二叉搜索树中的插入操作701二、删除二叉搜索树中的节点力扣450三、修剪二叉搜索树力扣669四、将有序数组转换为二叉搜索树力扣108 一、二叉搜索树中的插入操作701 /*** 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(rootNULL){TreeNode * inSertVal new TreeNode(val);return inSertVal;}if(valroot-val){// 往右插root-right insertIntoBST(root-right,val);}else{root-left insertIntoBST(root-left, val);}return root;}
};二、删除二叉搜索树中的节点力扣450
/*** 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) {// 1.没找到值if(rootNULL) return NULL;if(root-valkey){// 2. 左右子树都为空if(root-leftNULLroot-rightNULL) {delete root;return NULL;}// 3. 左子树为空 右子树不为空else if(root-leftNULLroot-right!NULL){TreeNode * Rresult root-right;delete root;return Rresult;}// 4. 左子树不为空右子树为空else if(root-left!NULLroot-rightNULL){TreeNode * Rresult root-left;delete root;return Rresult;}// 5. 左右字数都不为空else{// 把左子树接到右子树最左侧TreeNode * Tright root-right;// 5.1 找到右子树的最左侧while(Tright-left!NULL){Tright Tright-left;}// 5.2 把左子树接到右子树最左侧Tright-left root-left;// 5.3 返回右子树TreeNode * Rresult root-right;delete root;return Rresult;}}else if(root-valkey){root-right deleteNode(root-right,key);}else{root-left deleteNode(root-left,key);}return root;}
};三、修剪二叉搜索树力扣669 /*** 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(rootNULL) return NULL;if(root-vallow){// 删除所有左子树// 继续向右遍历TreeNode* Tright trimBST(root-right,low,high);return Tright;}else if(root-valhigh){// 删除右子树TreeNode* Tleft trimBST(root-left,low,high);return Tleft;}root-left trimBST(root-left,low,high);root-right trimBST(root-right,low,high);return root;}
};四、将有序数组转换为二叉搜索树力扣108 /*** 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* sortedArrayToBST(vectorint nums) {TreeNode * root traversal(nums,0,nums.size()-1);return root;}TreeNode* traversal(vectorint nums,int left,int right){if(leftright) return NULL;int mid (leftright)/2;TreeNode * root new TreeNode(nums[mid]);root-left traversal(nums,left,mid-1);root-right traversal(nums,mid1,right);return root;}
};
