本文关键词：算法题，刷题，Leetcode, 力扣，二叉搜索树，BST，第 k 小的元素，Python, C++, Java

题目地址：https://leetcode.com/problems/kth-smallest-element-in-a-bst/#/descriptionopen in new window

题目描述

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.

Example 1:

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
Output: 3

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中第K小的数字是多少。

解题方法

各位题友大家好！ 我是负雪明烛。

今天题目重点只有一个：二叉搜索树（BST）。

遇到二叉搜索树，立刻想到这句话：

「二叉搜索树（BST）的中序遍历是有序的」。

这是解决所有二叉搜索树问题的关键。

题目要求 BST 中第 k 小的元素，等价于求 BST 中序遍历的第 k 个元素。

分享二叉树遍历的模板：先序、中序、后序遍历方式的区别在于把「执行操作」放在两个递归函数的位置。

伪代码在下面。

1、 先序遍历：

def dfs(root):
    if not root:
        return
    执行操作
    dfs(root.left)
    dfs(root.right)

1 2 3 4 5 6

1、 中序遍历：

def dfs(root):
    if not root:
        return
    dfs(root.left)
    执行操作
    dfs(root.right)

1 2 3 4 5 6

1、 后序遍历：

def dfs(root):
    if not root:
        return
    dfs(root.left)
    dfs(root.right)
	执行操作

1 2 3 4 5 6

本题是使用了中序遍历，所以把「执行操作」这一步改成自己想要的代码。

于是有了下面两种写法。

方法一：数组保存中序遍历结果

这个方法是最直观的，也最不容易出错的。

1、 先中序遍历，把结果放在数组中；
2、 最后返回数组的第k个元素；

对应的代码如下，二叉树的各种遍历方式是基本功，务必要掌握。

Java 代码如下：

public class Solution {
    List<Integer> list;
    public int kthSmallest(TreeNode root, int k) {
        list = new ArrayList<Integer>();
        dfs(root);
        return list.get(k - 1);
    }
    public void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

C++代码如下：

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> res;
        dfs(root, res);
        return res[k - 1];
    }
    void dfs(TreeNode* root, vector<int>& res) {
        if (!root) return;
        dfs(root->left, res);
        res.push_back(root->val);
        dfs(root->right, res);
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Python 语言如下：

class Solution(object):
    def kthSmallest(self, root, k):
        res = []
        self.dfs(root, res)
        return res[k - 1]
    
    def dfs(self, root, res):
        if not root: return
        self.dfs(root.left, res)
        res.append(root.val)
        self.dfs(root.right, res)

1 2 3 4 5 6 7 8 9 10 11

复杂度分析：

• 时间复杂度：O(N)，因为每个节点只访问了一次；
• 空间复杂度：O(N)，因为需要数组保存二叉树的每个节点值。

方法二：只保存第 k 个节点

在方法一中，我们保存了整个中序遍历数组，比较浪费空间。

其实我们只需要知道，在中序遍历的时候，第 k 个被访问的节点即可。访问到第 k 个节点后，递归终止，后面的节点就不用访问了。

下图展示了中序遍历过程中的节点访问顺序。

具体的做法中，我们需要需要两个变量：

1、 用一个全局变量保存最终的结果；
2、 用一个全局变量保存当前访问到第几个节点；

如果不使用全局变量，而是使用函数传参，需要注意「值传递」和「引用传递」的区别：

值传递：每个递归的内部都需要对同一个变量修改，如果用普通函数的传参，对于 int 型的参数，使用的是值传递，即拷贝了一份传到了函数里面。那么函数里面对 int 型的修改不会影响外边的变量。

使用全局变量，可以保证递归函数的每次修改都是反映到全局的，从而保证遍历到第 k 个的时候，所有的递归立刻停止。

Java 代码如下：

public class Solution {
    int res;
    int count;
    
    public int kthSmallest(TreeNode root, int k) {
        res = 0;
        count = k;
        dfs(root);
        return res;
    }
    public void dfs(TreeNode root){
        if(root == null){
            return;
        }
        dfs(root.left);
        count--;
        if(count == 0){
            res = root.val;
            return;
        }
        dfs(root.right);
    }
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

C++代码如下：

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        count = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode* root) {
        if (!root) return;
        dfs(root->left);
        count -= 1;
        if (count == 0) {
            res = root->val;
            return;
        }
        dfs(root->right);
    }
private:
    int res;
    int count;
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Python 代码如下：

class Solution(object):
    def kthSmallest(self, root, k):
        self.res = 0
        self.count = k
        self.dfs(root)
        return self.res
    
    def dfs(self, root):
        if not root: return
        self.dfs(root.left)
        self.count -= 1
        if self.count == 0:
            self.res = root.val
            return
        self.dfs(root.right)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

复杂度分析：

• 时间复杂度：O(k)，因为只访问了前 k 个节点；
• 空间复杂度：O(h)，其中 h 为树的高度，因为递归用了系统栈，而栈的深度最多只有树的高度。

迭代

待补。

总结

1、 二叉树的多种遍历方式必须要掌握；
2、 一定切记：二叉搜索树的中序遍历是有序的；
3、 另外建议刚开始刷题的朋友，不妨从二叉树上手；

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发