62.二叉搜索树的第k个节点

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def KthNode(self, pRoot, k):
        # write code here
        if not pRoot:
            return None
        ret = []
        def inOrder(root):
            if not root:
                return None
            inOrder(root.left)
            ret.append(root)
            inOrder(root.right)
            return ret
        result = inOrder(pRoot)
        if 0<k<=len(result):
            return result[k-1]
        else:
            return None