29.二叉搜索树中第K小的元素
（拼多多二面）给定一个二叉搜索树的根节点
root，和一个整数k，请你设计一个算法查找其中第k小的元素（从 1 开始计数）。输入：[3,1,4,null,2], k = 1 输出：1 3 / \ 1 4 \ 2
本题难度较低，考察对二叉树的中序遍历，二叉搜索树中序遍历后的结果就是递增的一个序列，取其中的第k个即可。
后续追问1：如果你需要频繁地查找第 k 小的值，你将如何优化算法？
将【以每个结点为根结点的子树的结点数】存在哈希表中unordered_map nodeNum。
记录下以每个结点为根结点的子树的结点数，从根节点开始，对当前结点 node 进行如下操作：
- 如果 node 的左子树的结点数 left 小于 k−1，则第 k 小的元素一定在 node 的右子树中，令 node 等于其的右子结点，k 等于 k−left−1，并继续搜索；
- 如果 node 的左子树的结点数 left 等于 k−1，则第 k 小的元素即为 node ，结束搜索并返回 node 即可；
- 如果 node 的左子树的结点数 left 大于 k−1，则第 k 小的元素一定在 node 的左子树中，令 node 等于其左子结点，并继续搜索。
后续追问2：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？
将二叉搜索树变为平衡二叉搜索树。