題目：
給定一個二元搜尋樹 (BST)，請找出其中第 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

提示：

• 樹中的節點數量 n 在範圍 [1, 10^4] 內。
• 1 <= k <= n <= 10^4
• 節點數值是唯一的。

解題思路

直接用暴力法，遍歷所有節點存到一個陣列再排序，然後回傳第k個結果，再看看有沒有其他優化方式。

BFS 迭代版本

用BFS遍歷所有節點存到一個陣列再排序，然後回傳第k個結果。

實作：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        
        vector<int> res;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            // 處理當前節點的資料
            res.push_back(node->val);

            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }

        sort(res.begin(), res.end());
        return res[k-1];
    }
};

但我覺得事情沒有這麼單純，那這樣這題難度應該變Easy，速度上能不能再更快呢？

DFS 遞迴版本

能不能少掉 sort 排序呢？用中序 in order DFS遍歷的話，就可以得到由小到大的序列，那就可以少掉 sort 排序，

實作：

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> res;
        inOrderDFS(root, res);
        return res[k-1];
    }

    void inOrderDFS(TreeNode* root, vector<int>& res) {
        if (root == nullptr)
            return;

        inOrderDFS(root->left, res);

        // 處理當前節點的資料
        res.push_back(root->val);

        inOrderDFS(root->right, res);
    }
};

還可以再優化嗎？由於中序遍歷的結果是由小到大放入的，所以累積到第k次時就可以獲得最終答案，那麼就可以提早結束，減少運算時間。

實作：

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> res;
        int count = k;
        inOrderDFS(root, res, count);
        return res[k-1];
    }

    void inOrderDFS(TreeNode* root, vector<int>& res, int& count) {
        if (root == nullptr)
            return;

        inOrderDFS(root->left, res, count);

        // 處理當前節點的資料
        res.push_back(root->val);
        count--;
        if (count == 0)
            return;

        inOrderDFS(root->right, res, count);
    }
};

還可以優化嗎？那結果只是回傳第k次的值(由小到大)的話，還需要陣列存放結果嗎？好像也可以省起來！

實作：

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int res;
        int count = k;
        inOrderDFS(root, count, res);
        return res;
    }

    void inOrderDFS(TreeNode* root, int& count, int& res) {
        if (root == nullptr)
            return;

        inOrderDFS(root->left, count, res);

        // 處理當前節點的資料
        count--;
        if (count == 0) {
            res = root->val;
            return;
        }

        inOrderDFS(root->right, count, res);
    }
};

DFS 迭代版本

上面是 DFS 遞迴版本，這邊練習迭代版本，

實作：

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* curr = root;

        while (curr != nullptr || !stk.empty()) {
            while (curr != nullptr) {
                stk.push(curr);
                curr = curr->left;
            }

            curr = stk.top();
            stk.pop();

            // 處理當前節點的資料
            res.push_back(curr->val);

            curr = curr->right;
        }

        return res[k-1];
    }
};

這是DFS迭代版本優化後的提早結束版本，

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int res;
        stack<TreeNode*> stk;
        TreeNode* curr = root;

        while (curr != nullptr || !stk.empty()) {
            while (curr != nullptr) {
                stk.push(curr);
                curr = curr->left;
            }

            curr = stk.top();
            stk.pop();

            // 處理當前節點的資料
            k--;
            if (k == 0) {
                res = curr->val;
                break;
            }

            curr = curr->right;
        }
        return res;
    }
};

參考：
#230. Kth Smallest Element in a BST