LC 230二叉搜索树中第 K 小的元素Kth Smallest Element in a BST　中等

返回二叉搜索树中第 k 小的节点值。

思路 迭代中序遍历天然升序，每弹栈一个 k 减 1，减到 0 即答案。时间 O(h+k)。

class Solution:
    def kthSmallest(self, root, k):
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right
        return -1