leetcode 230. Kth Smallest Element in a BST 二叉搜索树BST的中序遍历是有序序列

今天药忘吃喽~ 2022-06-08 12:08 144阅读 0赞

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:  
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Follow up:  
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

**考察要点：二叉搜索树BST的中序遍历可以得到一个有序的序列。**

所以DFS深度优先遍历遍历即可。

代码如下：

import java.util.ArrayList;
    
    /*class TreeNode 
    {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
    }*/
    
    /*
     * 这道题的关键就是BST的中序遍历得到的就是排序好的数组
     * 这个是k小元素，我们的得到的是从小到大的元素（优先遍历左结点，然后右结点）
     * 假如是k大元素，直接邮箱遍历右结点，然后是左结点，同样如此
     * 
     * */
    public class Solution 
    {
        public int kthSmallest(TreeNode root, int k) 
        {
            if(root==null || k<=0)
                return -1;
            ArrayList<Integer> one=new ArrayList<>();
            getKSmall(root,one,k);       
            return one.get(k-1);
        }
    
        public void getKSmall(TreeNode root, ArrayList<Integer> one,int k) 
        {
            if(root!=null)
            {
                getKSmall(root.left, one,k);
    
                one.add(root.val);
                if(one.size()==k)
                    return;
    
                getKSmall(root.right, one,k);
            }
        }
    }

下面是C++的做法，就是一个简单的DFS深度优先遍历的应用，

**这道题最重要的事情就是要记住BFS二叉搜索树的中序遍历的结果是一个有序序列**

代码如下：

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <string>
    #include <map>
    
    using namespace std;
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution
    {
    public:
        vector<int> res;
        int kthSmallest(TreeNode* root, int k)
        {
            getAll(root, k);
            return res[k - 1];
        }
    
        void getAll(TreeNode* root, int k)
        {
            if (root != NULL)
            {
                getAll(root->left,k);
                res.push_back(root->val);
                if (res.size() == k)
                    return;
                getAll(root->right,k);
            }
        }
    };