230 二叉搜尋樹中第K小的元素（BST的中序周遊）

1. 問題描述：給定一個二叉搜尋樹，編寫一個函數 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

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst

2. 思路分析：

① 題目中給出了一個比較重要的條件，那就是二叉搜尋樹，結合題目中需要求解出樹中第k小的數字那麼可以想到二叉搜尋樹的一個性質：二叉搜尋樹的中序周遊是升序的，利用這個特點就可以求解出第k小的數字了，二叉樹的周遊都是遞歸調用左右子樹的，而中序周遊則是在調用完左子樹之後對目前的根節點進行處理的，是以我們可以在調用完左子樹之後進行處理，這裡進行計數就可以了，這裡可以聲明兩個類屬性：一個用來記錄中序周遊之後目前計數的個數，第二個是用來标記是否已經找到第k小的數字，假如找到了那麼就可以不往下進行遞歸了

② 需要注意的是在使用類名來通路屬性的時候送出上去是錯誤的，後面修改為self來通路類屬性就可以通過了

3. 代碼如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    count, res, flag = 0, 0, 0

    def inOrder(self, root: TreeNode, k: int):
        # flag = 1表示找到了
        if self.flag == 1 or not root: return
        # 中序周遊是在調用的中間位置進行處理的
        self.inOrder(root.left, k)
        # 退回到目前的root節點那麼表示的是中序周遊的通路順序這個時候進行計數就可以了
        self.count += 1
        if self.count == k:
            self.res = root.val
            self.flag = 1
            # 找到了就直接return傳回到上一層了
            return
        self.inOrder(root.right, k)

    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.inOrder(root, k)
        return self.res
           

可以寫一個有傳回值的遞歸方法這樣在找到第K小的元素之後可以直接傳回：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    count = 0
    res = 0

    # dfs方法可以傳回一個布爾值這樣在找到目前的第k個數字之後那麼就可以直接傳回了
    def dfs(self, root: TreeNode, k: int) -> bool:
        if not root: return False
        if self.dfs(root.left, k): return True
        if self.count + 1 == k:
            self.res = root.val
            return True
        self.count += 1
        # 左邊沒有找到那麼找右邊
        return self.dfs(root.right, k)

    def kthSmallest(self, root: TreeNode, k: int) -> int:
        self.dfs(root, k)
        return self.res
           

力扣官方提供的直接搜尋整個二叉搜尋樹的代碼：

class Solution:
    def kthSmallest(self, root, k):
        def inorder(r):
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []
        return inorder(root)[k - 1]