题目描述：给定一棵二叉搜索树，请找出其中的第 k 小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为 4。
Solutions
# -*- 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 pRoot is None or k <= 0:
return None
stack = []
node = pRoot
res = []
while node is not None or len(stack) > 0:
if node is not None:
stack.append(node)
node = node.left
else:
node = stack.pop()
res.append(node)
node = node.right
if len(res) < k:
return None
return res[k-1]
# 运行时间：28ms
# 占用内存：5720k
为了不要总在编程上纠结太久，可以用下面的方式，将中序遍历看成内部函数：
# -*- 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 pRoot is None or k <= 0:
return None
res = []
def inorder(root):
if root is None:
return
inorder(root.left)
res.append(root)
inorder(root.right)
inorder(pRoot)
if len(res) < k:
return None
return res[k-1]
# 运行时间：35ms
# 占用内存：5624k