[TOC]
一、二叉搜索树的增删改查
700. 二叉搜索树中的搜索（简单难度）
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
//终止条件
if(root==NULL)return NULL;
//处理节点
if(root->val==val) return root;
//有条件的递归调用
if(val<root->val)return searchBST(root->left,val);
if(val>root->val)return searchBST(root->right,val);
return root;
}
};
701. 二叉搜索树中的插入操作（中等难度）
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
//终止条件和处理节点
if(root==NULL){
TreeNode* newNode=new TreeNode(val);
return newNode;
}
//有条件的递归
if(val<root->val) root->left=insertIntoBST(root->left,val);
if(val>root->val) root->right=insertIntoBST(root->right,val);
return root;
}
};
450. 删除二叉搜索树中的节点（中等难度）
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
//终止条件（如果没有找到删除节点）
if(root==NULL) return NULL;
//处理节点（如果找到删除节点）
if(root->val==key){
//如果删除节点是叶子节点,返回NULL
if(root->left==NULL&&root->right==NULL) return NULL;
//如果删除节点只有右节点，返回右节点
else if(root->left==NULL&&root->right!=NULL)return root->right;
//如果删除节点只有左节点，返回左节点
else if(root->left!=NULL&&root->right==NULL)return root->left;
//如果删除节点有左节点和右节点，删除root，右节点替补，左节点接到右节点的最左侧节点上
else{
//找到其右子树的最左侧节点
TreeNode* cur=root->right;
while(cur->left!=NULL){
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;
}
};
669. 修剪二叉搜索树（中等难度）
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
//终止条件
if(root==NULL)return NULL;
//当前值需要裁剪
if(root->val<low)//如果当前值小于裁剪区间，说明需要修剪
{
return trimBST(root->right,low,high);//左节点一定不符合，只需要检查右节点
}
else 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;
}
};
二、二叉搜索树的最近公共祖先
235. 二叉搜索树的最近公共祖先（简单难度）
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先（简单难度）
方法一：直接使用普通二叉树的方法
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL) return NULL;
if(root->val==p->val||root->val==q->val) return root;
// 有条件递归
TreeNode* left=lowestCommonAncestor(root->left,p,q);
TreeNode* right=lowestCommonAncestor(root->right,p,q);
if(left!=NULL&&right!=NULL) return root;
if(left!=NULL&&right==NULL) return left;
if(left==NULL&&right!=NULL) return right;
return NULL;
}
};
方法一：有序递归子区间
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL)return NULL;
//如果p和q的值都小于当前节点的值，说明最近公共祖先在当前节点的左子树上
if(p->val<root->val&&q->val<root->val) return lowestCommonAncestor(root->left,p,q);
//如果p和q的值都小于当前节点的值，说明最近公共祖先在当前节点的右子树上
if(p->val>root->val&&q->val>root->val) return lowestCommonAncestor(root->right,p,q);
//否则说明最近公共祖先就是当前节点
return root;
}
};
897. 递增顺序搜索树（简单难度）
剑指 Offer II 052. 展平二叉搜索树（简单难度）
class Solution {
public:
TreeNode* pre;
void dfs(TreeNode* cur){
if(cur==nullptr) return;
dfs(cur->left);
// 处理节点
pre->right=cur;
cur->left=nullptr;
pre=cur;
dfs(cur->right);
}
TreeNode* increasingBST(TreeNode* root) {
TreeNode* myHead=new TreeNode(-1);
pre=myHead;
dfs(root);
return myHead->right;
}
};
剑指 Offer 54. 二叉搜索树的第k大节点（简单难度）
class Solution {
public:
int res=0;//最终结果
int count=0;//计数
void dfs(TreeNode* root,int k){
if(root==NULL) return ;
//倒序：右，根，左
dfs(root->right,k);
++count;
if(k==count) {
res=root->val;
return;
}
dfs(root->left,k);
}
int kthLargest(TreeNode* root, int k) {
dfs(root,k);
return res;
}
};
230. 二叉搜索树中第K小的元素（中等难度）
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
class Solution {
public:
int res=0;//最终结果
int count=0;//计数
void dfs(TreeNode* root,int k){
if(root==NULL) return ;
//正序：左，根，右
dfs(root->left,k);
// 进入节点
++count;
if(k==count) {
res=root->val;
return;
}
dfs(root->right,k);
}
int kthSmallest(TreeNode* root, int k) {
dfs(root,k);
return res;
}
};
剑指 Offer 33. 二叉搜索树的后序遍历序列（中等难度）
class Solution {
public:
// 后序遍历序列[左子树区间，右子树区间，根节点]
bool verifyPostorder(vector<int>& postorder) {
return dfs(postorder,0,postorder.size()-1);
}
// 在[left,right]中进行递归遍历，
bool dfs(vector<int>& postorder,int left,int right){
// 终止条件（right是根节点，此时只有一个节点）
if(left>=right) return true;
// 遍历[left,right]，查找第一个大于根节点的节点,此为右区间第一个节点
int m=left;
while(m<=right){
if(postorder[m]>=postorder[right]) break;
else m++;
}
// 遍历右子树区间[m,right-1]，查看是否有比right小的值
for(int i=m;i<right;i++){
if(postorder[i]<=postorder[right])
return false;
}
// 继续遍历左子树区间[left,m-1]和右子树区间[m,right-1]
return dfs(postorder,left,m-1)&&dfs(postorder,m,right-1);
}
};
285. 二叉搜索树中的中序后继（中等后继）
剑指 Offer II 053. 二叉搜索树中的中序后继（中等后继）
class Solution {
public:
vector<TreeNode*> arr;//中序遍历数组
void dfs(TreeNode* root){
if(root==NULL) return;
dfs(root->left);
arr.push_back(root);
dfs(root->right);
}
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
// 中序递归，得到数组
dfs(root);
// 遍历数组，找到该节点
int i=0;
while(i<arr.size()&&arr[i]->val!=p->val)++i;
// 如果i正好是最后一个节点，返回null
if(i==arr.size()-1) return NULL;
// 如果i不是最后一个节点，返回其后继
else return arr[i+1];
}
};
三、中序遍历相关
98. 验证二叉搜索树（中等难度）
class Solution {
public:
vector<int> arr;
void dfs1(TreeNode* root){
if(root==nullptr) return;
dfs1(root->left);
arr.push_back(root->val);
dfs1(root->right);
}
long long maxVal = LONG_MIN; // 左子树中的默认最大值，测试数据中有LONG_MIN
bool dfs2(TreeNode* root){
if(root==nullptr) return true;
bool left=dfs2(root->left);
// 中序遍历，maxVal为left子树中的最大值
if (maxVal < root->val) maxVal = root->val;
else return false;
bool right=dfs2(root->right);
return left&&right;
}
bool isValidBST(TreeNode* root) {
// 方法一
// dfs1(root);
// for(int i=1;i<arr.size();++i){
// if(arr[i-1]>=arr[i]) return false;
// }
// return true;
// 方法二
return dfs2(root);
}
};
426. 将二叉搜索树转化为排序的双向链表（中等难度）
class Solution {
private:
Node* pre=NULL; // 当前访问节点的前一个节点
Node* head=NULL;// 双向循环链表的头结点
public:
Node* treeToDoublyList(Node* root) {
if(root==NULL) return NULL;
// 采用中序遍历的方式遍历二叉搜索树，修改为双向链表
dfs(root);
// 修改为循环链表
head->left = pre;//头结点指向尾结点
pre->right = head;//尾结点指向头结点
return head;
}
// 中序遍历
void dfs(Node* cur){
// 终止条件
if(cur==NULL) return;
// 递归左节点
dfs(cur->left);
// 处理节点head,pre,cur
if(pre) pre->right=cur;// 如果pre不为空，说明双向链表上已经有节点，其指向当前节点
else head=cur;// 如果pre为空，说明双向链表没有节点，设置头结点
cur->left=pre;// 当前节点指向上一个
pre=cur;// 更新上一个节点
// 递归右节点
dfs(cur->right);
}
};