题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
解题思路
二叉树的中序遍历。
代码
Python(2.7.3)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23# -*- 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
res = []
global res
self.inOrder(pRoot)
if k < 1 or len(res) < k:
return None
return res[k - 1]
def inOrder(self, pRoot):
if pRoot is None:
return
self.inOrder(pRoot.left)
res.append(pRoot)
self.inOrder(pRoot.right)运行时间：42ms占用内存：5708k