题目描述

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?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

找出BST（二叉查找树）第K小的元素

解法

BST 也就是满足 左子树 < 根 < 右子树 条件的二叉树。因此，我们用中序遍历即可以得到从小到大排列的元素数组，题目要求返回第K小的元素，即我们只要遍历到第K个元素即可。 用常规的递归遍历代码实现快，但是程序运行速度较慢（中国版leetcode 10%），用迭代法遍历代码实现有难度，比较考验代码功底，但程序运行速度快（中国版Leetcode 70%）。

代码

 // 递归
 void traversalInorder(TreeNode* root, vector& result, int k) {
     if (result.size() == k || root == NULL) {
         return;
     }
     traversalInorder(root->left, result, k);
     result.emplace_back(root->val);
     traversalInorder(root->right, result, k);
 }

 // 迭代
void traversalInorder(TreeNode* root, vector& result, int k) {
    stack stack_;
    auto node = root;
    while(node || !stack_.empty()) {
        while(node) {
            if (node->left) {
                stack_.push(node);
                node = node->left;
            } else {
                result.emplace_back(node->val);
                if (result.size() == k)
                    return;
                node = node->right;
            }
        }
        if (!stack_.empty()) {
            node = stack_.top();
            stack_.pop();
            result.emplace_back(node->val);
            if (result.size() == k)
                return;
            node = node->right;
        }
    }
}

int kthSmallest(TreeNode* root, int k) {
    vector result;
    traversalInorder(root, result, k);
    return result[k-1];    
}