230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

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?

Constraints:

• The number of elements of the BST is between 1 to 10^4.
• You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

---

给定一棵二叉搜索树，问树中第k小的元素是哪个。 因为BST的特点是左<=根<=右，所以对树中序遍历之后就得到升序序列，取出第k个元素即可。代码如下：

class Solution {
private:
    void inOrder(TreeNode* root, int& k, int& target)
    {
        if (k < 0)
            return;
        if (root->left)
            inOrder(root->left, k, target);
        –k;
        if (k == 0)
            target = root->val;
        if (root->right)
            inOrder(root->right, k, target);
    }
public:
    int kthSmallest(TreeNode* root, int k)
    {
        int target;
        inOrder(root, k, target);
        return target;
    }
};

本代码提交AC，用时26MS，时间复杂度是O(k)。
Follow up指出如果可以修改节点，怎样才能使得复杂度降低到O(height of tree)，可以给每个节点增加一个属性rank：左子树节点个数，该属性的含义就是小于该节点的节点个数，也即当前节点在中序遍历中的位置（rank）。查找的过程就类似二分了，从根节点开始，如果k小于当前节点的rank，说明第k小的数在左子树；如果k大于当前节点的rank，说明第k小的数在右子树；如果k==rank，则当前节点就是第k小的数。这样的查找过程就是不断的在当前节点选择走左子树还是右子树，走过的节点最多是树的高度。
rank属性可以在建BST时完成。