一、思路

二叉搜索树的中序遍历结果正好是从小到大排序好的，按照中序遍历顺序找第k个节点。

例如二叉搜索树（20，10，30，2，11，24，38）中第三小结点的值为11。

二、代码

public Solution {

public static void main(String[] args) {

//构建二叉搜索树

TreeNode root = new TreeNode(20);

root.left = new TreeNode(10);

root.right = new TreeNode(30);

root.left.left = new TreeNode(2);

root.left.right = new TreeNode(11);

root.right.left = new TreeNode(24);

root.right.right = new TreeNode(38);

Solution solution = new Solution();

//获取第3小的节点

int k=3;

TreeNode node = solution.getKthNode(root,k);

if (null!=node) {

System.out.println("找到第"+k+"小的节点值为："+node.value);

} else {

System.out.println("未找到第"+k+"小的节点");

}

}

//节点类

public static TreeNode {

int value;

TreeNode left;

TreeNode right;

TreeNode(int value) {

this.value = value;

}

}

//计数器

private int index = 0;

/**

* 获取二叉搜索树中第k个节点的对象

* @param root  二叉树根节点

* @param k     要查的节点位置k

* @return      第k个节点对象，若存在则返回，不存在则返回null

*/

public TreeNode getKthNode(TreeNode root, int k){

if(root != null){

//            先查左子树的第k小的节点

TreeNode node = getKthNode(root.left,k);

//            若左子树中查到则直接返回

if(node != null) {

return node;

}

index ++;

//命中索引为k的节点，直接返回

if(index == k) {

return root;

}

//            再查右子树的第k小的节点

node = getKthNode(root.right,k);

//            若右子树中查到则直接返回

if(node != null) {

return node;

}

}

return null;

}

}

微风不燥，阳光正好，你就像风一样经过这里，愿你停留的片刻温暖舒心。

我是程序员小迷（致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分享），若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢，您的支持是我们为您提供帮助的最大动力。

欢迎关注。助您在编程路上越走越好！