题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
知识点
二叉搜索树
Qiang的思路
因为二叉搜索树具有左子树节点小于根节点，右子树节点大于根节点的特点，所以当采取中序遍历的时候，得到的遍历序列是非递减的。此时，只要找的第k个值就是我们需要的结果。但是实际上我们并不需要得到完整的遍历序列，我们只需要遍历k个节点就能得到需要的结果。因为采取中序遍历时遍历到的第k个节点就是结果。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回对应节点TreeNode
def getResult(self, pRoot, k):
if pRoot.left!=None:
node, k=self.getResult(pRoot.left, k)
if node!=None:
return node, k-1
if k==1:
return pRoot, k-1
k-=1
if pRoot.right!=None:
node, k=self.getResult(pRoot.right, k)
if node!=None:
return node, k-1
return None, k
def KthNode(self, pRoot, k):
# write code here
if pRoot==None or k<1:
return None
node, k=self.getResult(pRoot, k)
return node
这个题需要注意的是k的更新问题，没遍历完一个节点就需要对其做更新操作。
作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。
