python解法
题目描述
给定一棵二叉搜索树,请找出其中的第k小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为4。
限制:
k >= 0
考虑k=0和k大于二叉树长度的情况
思路:
中序遍历
# -*- 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): def midTravel(root): if not root: return midTravel(root.left) self.k -= 1 if self.k == 0: self.res = root elif self.k > 0: midTravel(root.right) if k == 0: return self.k = k midTravel(pRoot) if self.k <= 0: return self.res else: return