[LeetCode]Kth Smallest Element in a BST

典型的二分的题目，我们每一次找到当前节点左子树的size，根据size大小决定去左子树还是右子树继续寻找，或者当前节点就是我们要找的节点。时间复杂度O(n) = O(n / 2) + 1，那么对于每一层的递归，我们从上到下分别耗时n/2, n/4, n/8...1，求和之后为n，所以时间复杂度为O(n)，空间复杂度O(log n)。代码如下：

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	int kthSmallest(TreeNode* root, int k) {
	int left = size(root->left);
	if(k < left + 1)
	return kthSmallest(root->left, k);
	else if(k > left + 1)
	return kthSmallest(root->right, k - left - 1);
	else
	return root->val;
	}
	private:
	int size(TreeNode* root)
	{
	if(!root)return 0;
	return 1 + size(root->left) + size(root->right);
	}
	};

view raw Kth Smallest Element in a BST_1.cpp hosted with ❤ by GitHub

当然我们用Inorder Traversal也可以做，时间复杂度O(n)，空间复杂度O(log n)，代码如下：

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	int kthSmallest(TreeNode* root, int k) {
	int count = 0;
	stack<TreeNode*> st;
	TreeNode* curr = root;
	while(st.size() || curr)
	{
	while(curr)
	{
	st.push(curr);
	curr = curr->left;
	}
	if(++count == k)
	return st.top()->val;
	curr = st.top()->right;
	st.pop();
	}
	return -1;
	}
	};

view raw Kth Smallest Element in a BST_2.cpp hosted with ❤ by GitHub

Follow up是如果需要经常性地插入和删除，并且查询我们如何优化。我们在节点上存当前子树的大小即可，具体可以参考这篇文章。