python解法

题目描述

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

限制：

k >= 0
考虑k=0和k大于二叉树长度的情况

思路：

中序遍历

# -*- 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):
        def midTravel(root):
            if not root:
                return 
            midTravel(root.left)
            self.k -= 1
            if self.k == 0:
                self.res = root 
            elif self.k > 0:
                midTravel(root.right)
        if k == 0:
            return 
        self.k = k
        midTravel(pRoot)
        if self.k <= 0:
            return self.res
        else:
            return