230. 二叉搜索树中第K小的元素

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
你可以假设 k 总是有效的，1 <= k <= 二叉搜索树元素个数。

示例：

输入1：

root = [3,1,4,null,2], k = 1

   3
  / \
 1   4
  \
   2

输出1：

1

输入2：

root = [5,3,6,2,4,null,null,1], k = 3

       5
      / \
     3   6
    / \
   2   4
  /
 1

输出2：

3

解答：

递归解法：

def kthSmallest(self, root: TreeNode, k: int) -> int:
    def gen(root):
        if root is not None:
            yield from gen(root.left)
            yield root.val
            yield from gen(root.right)
    it = gen(root)
    for i in range(k):
        res = next(it)
    return res

非递归解法：

# 中序遍历法，二叉搜索树的中序遍历正好是从小到大排序。
def kthSmallest(self, root: TreeNode, k: int) -> int:
    count = 0
    p = root
    stack = []
    while(p or stack):
        while(p):
            stack.append(p)
            p = p.left
        p = stack.pop()

        count += 1
        if (count == k): return p.val

        p = p.right