---
tags: LeetCode
---

# 230. Kth Smallest Element in a BST
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?

輸入範本如下

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        
    }
}

### 直覺想法

1. 按照中序走訪 BST , 其數字會由小到大排列 , 因此只要全部走過一次 , 並且將值存入 List 中. 即可透過索引值去找到第 k 個小的數字

    112 ms	28.6 MB
    You are here!
    Your runtime beats 26.85 % of csharp submissions.
    public int KthSmallest(TreeNode root, int k)
    {
        List<int> list = new List<int>();
        TravelTree(root, list);
        return list[k - 1];

        void TravelTree(TreeNode node, List<int> collection)
        {
            if (node is null) return;
            TravelTree(node.left, collection);
            collection.Add(node.val);
            TravelTree(node.right, collection);
        }
    }

2. 搜尋方式採用使用 DFS , 走訪順序為中緒走訪 . 透過 k 去紀錄現在走到第幾個字 ,
- 使用遞迴

        92 ms	28.3 MB
        You are here!
        Your runtime beats 98.28 % of csharp submissions.
        public int KthSmallest(TreeNode root, int k)
        {
            return FindKthSmallest(root, ref k);

            int FindKthSmallest(TreeNode node, ref int target)
            {
                if (node is null) return -1;
                int v = FindKthSmallest(node.left, ref target);
                if (target == 0) return v; // 已經找到答案了 , 把答案上傳.
                if (--target == 0) return node.val; // 目前這個點是答案.
                return FindKthSmallest(node.right, ref target);
            }
        }

- 使用 Stack

        96 ms	28.2 MB
        You are here!
        Your runtime beats 94.09 % of csharp submissions.
        public int KthSmallest(TreeNode root, int k)
        {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode node = root;
            while (node != null || stack.Count != 0)
            {
                while (node != null)
                {
                    stack.Push(node);
                    node = node.left;
                }
                node = stack.Pop();
                if (--k == 0) return node.val;
                node = node.right;
            }
            throw new Exception("not found");
        }

3. 二分搜尋法 - 預先判斷左右子點的 node 數量 , 判斷第 K 小的數量在左右子樹哪一邊.
- 若左子樹有 k 個以上(含)的 node , 代表第 k 小的 node 在左子樹
- 若左子樹有 k - 1 個 node , 代表第 k 小的 node 是 root 自身
- 若左子樹有 k - 2 個以下(含) node , 代表第 k 小的 node 在右子樹

    100 ms	28.2 MB
    You are here!
    Your runtime beats 85.96 % of csharp submissions.
    public int KthSmallest(TreeNode root, int k)
    {
        int count = CountNode(root.left);
        if (k <= count)
        {
            return KthSmallest(root.left, k);
        }
        else if (k > count + 1)
        {
            return KthSmallest(root.right, k - (count + 1));
        }
        return root.val;

        int CountNode(TreeNode node)
        {
            return node is null ? 0 : 1 + CountNode(node.left) + CountNode(node.right);
        }
    }

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: