leetcode.png

題目

給定一個二叉搜索樹，編寫一個函數(shù) kthSmallest 來查找其中第 k 個最小的元素。

說明：
你可以假設(shè) k 總是有效的，1 ≤ k ≤ 二叉搜索樹元素個數(shù)。

示例 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

進(jìn)階：
如果二叉搜索樹經(jīng)常被修改（插入/刪除操作）并且你需要頻繁地查找第 k 小的值，你將如何優(yōu)化 kthSmallest 函數(shù)？

數(shù)據(jù)結(jié)構(gòu)定義

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

分析

這是一道中等難度的題，題解的關(guān)鍵詞是二叉搜索樹，二叉搜索樹相信大家都知道它的特征是，左子樹的任意結(jié)點(diǎn)值<根結(jié)點(diǎn)值<右子樹結(jié)點(diǎn)值。

要查找它的第K小的元素值，應(yīng)該怎么做呢？提到二叉樹，離不開遍歷問題，根據(jù)二叉搜索樹的特征，它的中序遍歷正好能得到一個有序列表。
如果遞歸地進(jìn)行中序遍歷，將彈出來的結(jié)果保存都列表中，那么得到的列表將是一個從小到大的有序列表，取第 k-1 個即可滿足要求。

實(shí)現(xiàn)

在最初的Python實(shí)現(xiàn)中，我采用了遞歸遍歷整個搜索二叉樹后直接返回第k-1個值的做法。

Python 實(shí)現(xiàn) 第一版

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)

結(jié)果

結(jié)果比較一般。
再思考多一步，既然二叉搜索樹中序遍歷是逆序的，那么直接遍歷到第k個就可以停止遍歷了。

Python 實(shí)現(xiàn) 第二版

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)

結(jié)果

速度的提升是比較明顯的。

微信公眾號: 程序員的碎碎念