[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)。代码如下：



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



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