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.

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:
Try to utilize the property of a BST.

Diffculty
Medium

Similar Problems
[LeetCode ] Binary Tree Inorder Traversal Medium

Analysis

这道题要求第 k 个最小的元素，我们知道，二叉树的遍历方式中，只有中序遍历会产生一个有序的数组，因此，解题的关键就是理解中序遍历。

Solutions

非递归解法

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int cnt = 0;
        stack<TreeNode*> s;
        TreeNode *p = root;
        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;
    }
};

递归解法

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

Reference