二叉搜索树的第k个节点

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

思路

这里先指明题目中蕴含的一个特点，二叉搜索书的中序遍历的顺序就是从小到大的排序顺序。
一个很简单的思路就是先把树中序遍历，然后取第k个值。
边界情况要分别注意k过小（为0）和过大（超过树的大小）。
针对树很大的情况，可以在每次向遍历结果中加入节点时判断一下是否是第k个。可以提前终止遍历。

代码

class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        if k == 0:
            return None
        stack = []
        root = pRoot
        result = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            node = stack.pop()
            result.append(node)
            if len(result) == k: #如果树很大，可以提前终止遍历
                return node
            root =node.right
        if k>len(result):
            return None
        return result[k-1]