博文中会简要介绍Leetcode P0230题目分析及解题思路。
“Kth Smallest Element in a BST”是一道难度中等的题目，主要考察在二叉搜索树中寻找一个给定的元素。这道题有两种比较主流的思路，一种是迭代的解法，另一种是递归的解法。
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
其实不论是迭代解法还是递归解法，归根到底都是在做中序遍历。使用栈结构的迭代算法在中序遍历的基础上并没有太大变化，所以这里重点讲一下递归的解法。以下的Java代码是迭代解法。
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new LinkedList<>();
TreeNode curr = root;
int count = 0;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.offerFirst(curr);
curr = curr.left;
}
curr = stack.pollFirst();
count += 1;
if (count == k)
return curr.val;
curr = curr.right;
}
return 0;
}
}
本题的递归解法相对于中序遍历的递归解法有些微区别。我们需要传入一个counter作为计数器来记录当前按序遍历过的数结点个数，当counter等于k时说明遍历到了指定的结点，则返回结点即可。
以下是C++的题解代码实现。
/**
* 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) {
int count = 0;
return this->_Search(root, count, k)->val;
}
private:
TreeNode* _Search(TreeNode *curr, int &count, const int K) {
if (!curr)
return nullptr;
TreeNode *ret = nullptr;
ret = this->_Search(curr->left, count, K);
if (ret)
return ret;
++count;
if (count == K)
return curr;
ret = this->_Search(curr->right, count, K);
return ret;
}
};