###### tags: `Leetcode` `medium` `tree` `python` `c++`

# 230. Kth Smallest Element in a BST

## [題目連結:] https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

## 題目:
Given the ```root``` of a binary search tree, and an integer ```k```, return the ```kth``` smallest value (**1-indexed**) of all the values of the nodes in the tree.

**Follow up**: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?


## 解題想法:
* 題目為BST之第K小數字
* inorder traversal即可
* Follow up還沒挑戰....
## Python: Sol1
* 懶人法: 遍歷所有點存於array，return array[k-1] 即可

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        self.res=[]
        self.inorder(root)
        return self.res[k-1]
    def inorder(self,root):
        if not root:
            return 
        self.inorder(root.left)
        self.res.append(root.val)
        self.inorder(root.right)

## Python: Sol2
* inorder遍歷同時將k遞減，判斷是否k==0，即為最終解

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        #inorder 第k個數
        self.k=k
        return self.inorder(root)
    
    def inorder(self,root):
        if not root:
            return -1
        #遍歷到最左了
        res=self.inorder(root.left)
        if res!=-1:
            return res
        self.k-=1
        if self.k==0:
            return root.val
        return self.inorder(root.right)

## Python: Sol3
* Iterative

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        stack=[]
        while stack or root:
            while root:
                stack.append(root)
                root=root.left
            root=stack.pop()
            k-=1
            if k==0:
                return root.val
            root=root.right

## C++: Sol1
* 同python Sol1

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        inorder(root);
        return res[k-1];
    }
    void inorder(TreeNode* root){
        if (root==nullptr)
            return;
        inorder(root->left);
        res.push_back(root->val);
        inorder(root->right);
    }

private:
    vector<int> res;
};

## C++: Sol2
* 同python Sol2

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        count=k;
        return inorder(root, count);
    }
private:
    int count;
    // &別名呼叫 避免浪費記憶體空間
    int inorder(TreeNode* root, int& count){
        if (root==nullptr)
            return -1;
        int res=inorder(root->left,count);
        if (res!=-1)
            return res;
        count-=1;
        if (count==0)
            return root->val;
        return inorder(root->right,count);
    }
};