初级数据结构——二叉搜索树题库（c++）
目录
- 前言
- [1.——108. 将有序数组转换为二叉搜索树](https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/)
- [2.——LCR 052. 递增顺序搜索树](https://leetcode.cn/problems/NYBBNL/)
- [3.——897. 递增顺序搜索树](https://leetcode.cn/problems/increasing-order-search-tree/)
- [4.——530. 二叉搜索树的最小绝对差](https://leetcode.cn/problems/minimum-absolute-difference-in-bst/)
- [5.——653. 两数之和 IV - 输入二叉搜索树](https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/)
- [6.——501. 二叉搜索树中的众数](https://leetcode.cn/problems/find-mode-in-binary-search-tree/)
- [7.——99. 恢复二叉搜索树](https://leetcode.cn/problems/recover-binary-search-tree/)
- [8.——99. 恢复二叉搜索树](https://leetcode.cn/problems/recover-binary-search-tree/)
- [9.——LCR 174. 寻找二叉搜索树中的目标节点
- [10.——1008. 前序遍历构造二叉搜索树](https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/description/)
- [11.——701. 二叉搜索树中的插入操作](https://leetcode.cn/problems/insert-into-a-binary-search-tree/)
- 结语
前言
通过上期（蓝色字体可以点进去）我们已经初步了解了二叉搜索树，那么这期我们就来进行实战，应用和巩固相关的知识点。
1.——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 {//平衡二叉树每个节点的左子树和右子树高度不超过一
TreeNode* sortedArray(vector<int>& nums,int l,int r){//l与r代表数组范围
if(l>r)return NULL;
int mid=(l+r)/2;//因为是有序数组构建平衡二叉树根节点一定为数字中间
TreeNode*node=new TreeNode(nums[mid]);
node->left=sortedArray(nums,l,mid-1);//它的左子树必然是从l到mid-1
node->right=sortedArray(nums,mid+1,r);
return node;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return sortedArray(nums,0,nums.size()-1);
}
};
2.——LCR 052. 递增顺序搜索树
/**
* 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 {
vector<int>ret;
void inOrder(TreeNode*root){
if(root){//中序遍历得到结果数组
inOrder(root->left);
ret.push_back(root->val);
inOrder(root->right);
}
}
public:
TreeNode* increasingBST(TreeNode* root) {
ret.clear();
inOrder(root);
TreeNode*head=new TreeNode();
TreeNode*curr=head;
for(int i=0;i<ret.size();i++){
TreeNode*t=new TreeNode(ret[i]);
curr->right=t;
curr=t;
}
return head->right;//结果二叉树就是虚拟节点head的右子树
}
};
3.——897. 递增顺序搜索树
/**
* 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 {//这题和上题的思路基本一样，不同的点就是在中序遍历过程中构造结果二叉树
TreeNode*curr;
void inOrder(TreeNode*root){
if(root){
inOrder(root->left);
curr->right=root;//递归到1这个节点
root->left=NULL;//因为结果二叉树的没有左子树所以左子树要致为空
curr=root;
inOrder(root->right);
}
}
public:
TreeNode* increasingBST(TreeNode* root) {
TreeNode*head=new TreeNode(0);
curr=head;
inOrder(root);
return head->right;
}
};
4.——530. 二叉搜索树的最小绝对差
/**
* 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 {
int ret,pre;
void inOrder(TreeNode*root){
if(root){
inOrder(root->left);
ret=min(ret,(root->val-pre));
pre=root->val;
inOrder(root->right);
}
}
public:
int getMinimumDifference(TreeNode* root) {
ret=100000000;//初始化一个很大的值用于第一次比较
pre=-10000000;
inOrder(root);
return ret;
}
};
5.——653. 两数之和 IV - 输入二叉搜索树
/**
* 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 {
vector<int>ret;
void inOrder(TreeNode*root){
if(root){
inOrder(root->left);
ret.push_back(root->val);
inOrder(root->right);
}
}
public:
bool findTarget(TreeNode* root, int k) {
ret.clear();
inOrder(root);
int l=0,r=ret.size()-1;
while(l<r){//这里面又有双指针的用法了，回顾一下
int sum=ret[l]+ret[r];
if(sum>k)r--;//如果相加的结果大于k那就是r指针往前跑，因为这是一个递增数列
else if(sum<k)l++;//与上同理
else return true;
}
return false;
}
};
6.——501. 二叉搜索树中的众数
/**
* 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 {
int pre;//代表上一次访问的节点值
int cnt,maxcnt;//cnt该节点代表当前出现的次数，maxcnt代表众数
vector<int>ret;
void visit(TreeNode*root){
if(root->val==pre)cnt++;//相等cnt++
else {//不相等pre变成当前节点的值
cnt=1;
pre=root->val;
}
if(cnt>maxcnt){//众数被刷新了
maxcnt=cnt;
ret.clear();//把原先结果数组的众数清楚掉，原先众数可能为多个
ret.push_back(root->val);//把新的众数插入数组
}else if(cnt==maxcnt){
ret.push_back(root->val);
}
}
void inOrder(TreeNode* root){
if(root){
inOrder(root->left);
visit(root);
inOrder(root->right);
}
}
public:
vector<int> findMode(TreeNode* root) {
ret.clear();
pre=-10000000;
cnt=maxcnt=0;
inOrder(root);
return ret;
}
};
7.——99. 恢复二叉搜索树
/**
* 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 {
vector<TreeNode*>ret;
void inOrder(TreeNode*root){
if(root){
inOrder(root->left);
ret.push_back(root);
inOrder(root->right);
}
}
public:
void recoverTree(TreeNode* root) {
ret.clear();
inOrder(root);
TreeNode*x=NULL;
TreeNode*y=NULL;
for(int i=0;i<ret.size()-1;i++){//中序遍历之后就是一个递增序列
if(ret[i]->val>ret[i+1]->val){
if(!x)x=ret[i];
y=ret[i+1];
}
}
if(x&&y){//和错误的两个节点的值交换就行
int t=x->val;
x->val=y->val;
y->val=t;
}
}
};
8.——99. 恢复二叉搜索树
/**
* 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 {
vector<TreeNode*>ret;
void inOrder(TreeNode*root){
if(root){
inOrder(root->left);
ret.push_back(root);
inOrder(root->right);
}
}
public:
//1 2 7 4 5 6 3 以这个序列为例
void recoverTree(TreeNode* root) {
ret.clear();
inOrder(root);
TreeNode*x=NULL;
TreeNode*y=NULL;
for(int i=0;i<ret.size()-1;i++){//中序遍历之后就是一个递增序列
if(ret[i]->val>ret[i+1]->val){
if(!x)x=ret[i];//x用于记录第一个错误位置
y=ret[i+1];//y记录第二个错误位置
}
}
if(x&&y){//和错误的两个节点的值交换就行
int t=x->val;
x->val=y->val;
y->val=t;
}
}
};
[9.——LCR 174. 寻找二叉搜索树中的目标节点
](https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/description/)
/**
* 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 {
vector<int> order;
void inOrder(TreeNode*root){
if(root){
inOrder(root->left);
order.push_back(root->val);
inOrder(root->right);
}
}
public:
int findTargetNode(TreeNode* root, int cnt) {
order.clear();
inOrder(root);
int n=order.size();
return order[n-cnt];//用数组总长度减去cnt编号就是结果，第一大就是倒数第一个，以此类推
}
};
10.——1008. 前序遍历构造二叉搜索树
/**
* 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 {
TreeNode* doConstructbst(vector<int>&preorder,int l,int r){
if(l>r)return NULL;
TreeNode*root=new TreeNode();
root->val=preorder[l];//前序遍历的根节点一定是数组第一个元素
int i;
for(i=l+1;i<=r;i++){//找到第一个大于根节点的值，从这个节点开始就是右子树
if(preorder[i]>root->val)break;
}
root->left=doConstructbst(preorder,l+1,i-1);//左子树
root->right=doConstructbst(preorder,i,r);//右子树
return root;
}
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
return doConstructbst(preorder,0,preorder.size()-1);
}
};
11.——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(!root){
return new TreeNode(val);//到这一步就是插入节点
}
if(val>root->val){
root->right=insertIntoBST(root->right,val);
}
else if(val<root->val) {
root->left=insertIntoBST(root->left,val);
}
return root;
}
};
结语
相信通过本期题库练习，大家对二叉搜索树的应用与理解又得到更深度理解，对于二叉搜索树的学习就告一段落了，下期我们一起来学习初级数据结构——领接矩阵，我们敬请期待。
关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家
