Leetcode 230. Kth Smallest Element in a BST

题目描述：找出二叉搜索树的第k小的值。

题目链接：Leetcode 230. Kth Smallest Element in a BST

思路：二叉搜索树是严格的左子树小于根、根小于右子树，中序遍历结果为从小到大的有序列表。
故用中序遍历结果，当ans有k个的时候，返回最后一个值。
当然也可以用递归的方式来做。

代码如下

class Solution:
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        #中序遍历结果 当为k的时候就可以返回值了。
        s = []
        curr = root
        ans = []
        while(s or curr):
            if curr:
                s.append(curr)
                curr = curr.left
            else:
                node = s.pop()
                ans.append(node.val)
                if len(ans)==k:
                    return ans[-1]
                curr = node.right
        return ans[k]

参考链接