【剑指offer】二叉搜索树的第k个节点

题目描述

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

思路

二叉搜索树的定义，根节点比左子树的节点都大，比右子树的节点都小
上述二叉搜索树的中序遍历为2345678

# -*- 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
ret = []

def preorder(pRoot):
if pRoot == None:
return None
preorder(pRoot.left)
ret.append(pRoot)
preorder(pRoot.right)

preorder(pRoot)
if len(ret) < k or k <= 0:
return None
return ret[k - 1]