LeetCode 每日一题 230. 二叉搜索树中第K小的元素

leetcode.png

题目

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:
输入: root = [3,1,4,null,2], k = 1

   3
  / \
 1   4
  \
   2

输出: 1

示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3

       5
      / \
     3   6
    / \
   2   4
  /
 1

**输出: **3

进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

---

数据结构定义

# Definition for a binary tree node.
class TreeNode:
     def __init__(self, x):
         self.val = x
         self.left = None
         self.right = None

---

分析

这是一道中等难度的题，题解的关键词是二叉搜索树，二叉搜索树相信大家都知道它的特征是，左子树的任意结点值<根结点值<右子树结点值。

要查找它的第K小的元素值，应该怎么做呢？提到二叉树，离不开遍历问题，根据二叉搜索树的特征，它的中序遍历正好能得到一个有序列表。
如果递归地进行中序遍历，将弹出来的结果保存都列表中，那么得到的列表将是一个从小到大的有序列表，取第 k-1 个即可满足要求。

---

实现

在最初的Python实现中，我采用了递归遍历整个搜索二叉树后直接返回第k-1个值的做法。

Python 实现 第一版

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        rs = []
        self.midVisit(root, rs)
        return rs[k-1]
    
    def midVisit(self, root: TreeNode, rs: list):
        if not root:
            return
        self.midVisit(root.left, rs)
        rs.append(root.val)
        self.midVisit(root.right, rs)

结果

结果比较一般。
再思考多一步，既然二叉搜索树中序遍历是逆序的，那么直接遍历到第k个就可以停止遍历了。

Python 实现 第二版

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        rs = []
        self.midVisit(root, rs, k)
        return rs[k-1]
    
    def midVisit(self, root: TreeNode, rs: list, k: int):
        if not root:
            return
        self.midVisit(root.left, rs, k)
        if len(rs)<k:
            rs.append(root.val)
        else:
            return
        self.midVisit(root.right, rs, k)

结果

速度的提升是比较明显的。

---

微信公众号: 程序员的碎碎念