给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。...1:
输入:root = [3,1,4,null,2], k = 1
输出:1
示例 2:
输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3
解题思路:
在二叉搜索树中...因此二叉搜索树具有一个重要性质:二叉搜索树的中序遍历为递增序列。
也就是说,本题可被转化为求中序遍历的第k个节点。
为求第k个节点,需要实现以下三项工作:
递归遍历时计数,统计当前节点的序号。...代码:
题目指出:
(二叉搜索树节点个数);因此无需考虑k > N的情况。 若考虑,可以在中序遍历完成后判断k>0是否成立,若成立则说明k > N。