230. Kth Smallest Element in a BST (Medium)

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.

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?

Hint:

1. Try to utilize the property of a BST.
2. What if you could modify the BST node's structure?
3. The optimal runtime complexity is O(height of BST).

Solution 1: iterative

这又是一道关于二叉搜索树 Binary Search Tree 的题， LeetCode中关于BST的题有Validate Binary Search Tree 验证二叉搜索树， Recover Binary Search Tree 复原二叉搜索树， Binary Search Tree Iterator 二叉搜索树迭代器， Unique Binary Search Trees 独一无二的二叉搜索树， Unique Binary Search Trees II 独一无二的二叉搜索树之二，Convert Sorted Array to Binary Search Tree 将有序数组转为二叉搜索树 和 Convert Sorted List to Binary Search Tree 将有序链表转为二叉搜索树。那么这道题给的提示是让我们用BST的性质来解题，最重要的性质是就是左<根<右，那么如果用中序遍历所有的节点就会得到一个有序数组所以解题的关键还是中序遍历啊。关于二叉树的中序遍历可以参见我之前的博客Binary Tree Inorder Traversal 二叉树的中序遍历，里面有很多种方法可以用，我们先来看一种非递归的方法：

int kthSmallest(TreeNode* root, int k) {
    stack<TreeNode*> s;
    TreeNode* p = root;
    int cnt = 0;
    while (p || !s.empty()) {
        while (p) {
            s.push(p);
            p = p->left;
        }
        p = s.top(); s.pop();
        ++cnt;
        if (cnt == k) return p->val;
        p = p->right;
    }
    return 0;
}

Solution 2:

当然，此题我们也可以用递归来解，还是利用中序in-order遍历来解，代码如下：

class Solution {
public:
    int intraverse(TreeNode* p, int& k) {
        if (!p) return 0;
        int val = intraverse(p->left, k);
        if (k == 0) return val;
        if (--k == 0) return p->val;
        return intraverse(p->right, k);
    }

    int kthSmallest(TreeNode* root, int k) {
        return intraverse(root, k);
    }
};

int kthSmallest(TreeNode* root, int& k) {
    if (root) {
        int x = kthSmallest(root->left, k);
        return !k ? x : !--k ? root->val : kthSmallest(root->right, k);
    }
    return -1;
}