題目描述
給定一棵二叉搜索樹程腹，請找出其中的第k小的結(jié)點(diǎn)钠四。例如， （5跪楞，3缀去，7，2甸祭，4缕碎，6，8） 中池户，按結(jié)點(diǎn)數(shù)值大小順序第三小結(jié)點(diǎn)的值為4咏雌。
思路
這里先指明題目中蘊(yùn)含的一個(gè)特點(diǎn)，二叉搜索書的中序遍歷的順序就是從小到大的排序順序校焦。
一個(gè)很簡單的思路就是先把樹中序遍歷赊抖，然后取第k個(gè)值。
邊界情況要分別注意k過姓洹（為0）和過大（超過樹的大蟹昭）。
針對樹很大的情況耸成，可以在每次向遍歷結(jié)果中加入節(jié)點(diǎn)時(shí)判斷一下是否是第k個(gè)报亩。可以提前終止遍歷井氢。
代碼
class Solution:
# 返回對應(yīng)節(jié)點(diǎn)TreeNode
def KthNode(self, pRoot, k):
if k == 0:
return None
stack = []
root = pRoot
result = []
while stack or root:
while root:
stack.append(root)
root = root.left
node = stack.pop()
result.append(node)
if len(result) == k: #如果樹很大弦追，可以提前終止遍歷
return node
root =node.right
if k>len(result):
return None
return result[k-1]
