「算法刷题」二叉搜索树专题汇总（力扣版）

本文记录作者刷题过程中与二叉搜索树相关的题目。

一、增删改查

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;
    }
};

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);
    }
};

四、后序遍历

剑指 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);

    }
};

五、不同的二叉搜索树

96. 不同的二叉搜索树（中等难度）

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。n的范围在[1,19]

输入：n = 3
输出：5

点评

class Solution {
public:
    /*动态规划题
    【状态定义】dp[i]表示i个节点的二叉搜索树的个数
    【状态转换】以dp[3]为例，dp[3]=元素1为根的个数+元素2为根的个数+元素3为根的个数
    元素1为根的个数=右子树有2个元素的个数*左子树有0个元素的个数=dp[2]*dp[0]
    元素2为根的个数=右子树有1个元素的个数*左子树有1个元素的个数=dp[1]*dp[1]
    元素3为根的个数=右子树有0个元素的个数*左子树有2个元素的个数=dp[0]*dp[2]
    得dp[3]==dp[2]*dp[0]+dp[1]*dp[1]+dp[0]*dp[2]
    假设j为根节点个数，范围在[1,i]
    则 dp[i]+=元素j为根的个数
    =右子树有i-j个元素的个数*左子树有j-1个元素的个数
    =dp[i-j]*dp[j-1]
    【初始状态】根据递推公式，dp[0]需要初始化
    dp[0]表示0个节点的二叉搜索树的个数，可以视为空树，设为1
    【遍历顺序】根据递推公式，dp[i]的推导依赖于j，dp[i-j]在dp[i]之前得出
    所以i的范围是正序，在[1,n]，j不能超过i，范围在[1,n]
    */
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        // i表示节点数,范围在[1,n]
        for (int i = 1; i <= n; i++) {
            // j表示j为根时的情况，范围在[1,i]
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];// 递归公式
            }
        }
        return dp[n];
    }
};

95. 不同的二叉搜索树 II（中等难度）

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回所有满足题意的二叉搜索树。n的范围在[1,8]

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

点评

该题和96的不同点在于，其需要返回所有不同的二叉搜索树，其n的范围缩小到8，就减少了计算量，可以用深度优先搜索。96中的动态规划无法用来求解该题。

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return dfs(1, n);
    }
    vector<TreeNode*> dfs(int start,int end){
        if(start>end) return {nullptr};
        vector<TreeNode*> resTrees;
        // 遍历所有为n的节点，作为当前的根节点
        for(int i=start;i<=end;++i){
             // 获得所有可行的左子树集合
            vector<TreeNode*> leftTrees = dfs(start, i - 1);
            // 获得所有可行的右子树集合
            vector<TreeNode*> rightTrees = dfs(i + 1, end);
            // 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
            for (auto& left:leftTrees) {
                for (auto& right:rightTrees) {
                    TreeNode* currTree = new TreeNode(i);
                    currTree->left = left;
                    currTree->right = right;
                    resTrees.emplace_back(currTree);//加入当前节点
                }
            }
        }
        return resTrees;
    }
};

六、有序数组

108. 将有序数组转换为二叉搜索树（简单难度）

    // 方法一：递归法
   TreeNode* sortedArrayToBST1(vector<int>& nums) {
    if(nums.size()==0)return NULL;
    //确定切割点
    int index = nums.size()/2;
    //构造根节点
    TreeNode* root=new TreeNode(nums[index]);
    //终止条件
    if(nums.size()==1)return root;
    //切割数组
    vector<int> leftNums(nums.begin(),nums.begin()+index);
    vector<int> rightNums(nums.begin()+index+1,nums.end());
    //递归调用
    root->left = sortedArrayToBST1(leftNums);
    root->right = sortedArrayToBST1(rightNums);
    return root;
}
// 方法二
TreeNode* preOrder(vector<int>& nums,int left,int right) {
    if(left>right)return NULL;
    //确定切割点
    int index = left + ((right - left) / 2);
    //构造根节点
    TreeNode* root=new TreeNode(nums[index]);
    //递归调用
    root->left = preOrder(nums,left,index-1);
    root->right = preOrder(nums,index+1,right);
    return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
    TreeNode* root = preOrder(nums, 0, nums.size() - 1);
    return root;
}

538. 把二叉搜索树转换为累加树（中等难度）

1038. 从二叉搜索树到更大和树（中等难度）

class Solution {
public:
    //反中序遍历
    void DinOrder(TreeNode* root,int& pre) { // 右中左遍历
        if(root==NULL) return;
        DinOrder(root->right,pre);//右
        root->val += pre;//当前新节点值=前一节点值+当前旧节点值
        pre = root->val;//更新前一节点值
        DinOrder(root->left,pre);//中
    }
    TreeNode* bstToGst(TreeNode* root) {
        int pre= 0;
        DinOrder(root,pre);
        return root;
    }
};

501. 二叉搜索树中的众数（简单难度）

class Solution {
public:
    //中序遍历数组
    void inOrder(TreeNode* node,TreeNode*& pre,int &curTimes,int& maxTimes,vector<int>& result){
        if(node==NULL) return;
        inOrder(node->left,pre,curTimes,maxTimes,result);
        //如果当前节点是第一个节点
        if (pre==NULL) curTimes=1;
        //如果当前节点值等于前一个节点值
        else if(node->val == pre->val) curTimes++;
        //如果当前节点值不等于前一个节点值
        else curTimes=1;
        pre = node;
        //如果当前计数大于最大计数
        if (curTimes > maxTimes){
            result.clear();
            result.push_back(node->val);
            maxTimes = curTimes;
        }
        //如果当前计数等于最大计数
        else if (curTimes == maxTimes) result.push_back(node->val);
        inOrder(node->right,pre,curTimes,maxTimes,result);
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> result;//众数数组
        TreeNode* pre=NULL;//前一个节点
        int curTimes=1;//计数器
        int maxTimes=0;//
        inOrder(root,pre,curTimes,maxTimes,result);
        return result;
    }
};

530. 二叉搜索树的最小绝对差（简单难度）

783. 二叉搜索树节点最小距离（简单难度）

class Solution {
public:
    //将搜索二叉树转换为有序数组
    void inOrder(TreeNode* root,TreeNode*& pre,int& result){
        if(root==NULL) return;
        inOrder(root->left,pre,result);
        //如果当前节点是第一个
        if(pre==NULL) result=INT_MAX;
        //如果当前节点不是第一个
        else result=min(result,root->val-pre->val);
        pre=root;//更新前一节点
        inOrder(root->right,pre,result);
    }
    int getMinimumDifference(TreeNode* root) {
        TreeNode* pre=NULL;//前一节点
        int result=INT_MAX;
        inOrder(root,pre,result);//获取有序数组
        return result;
    }
};