大厂面试：二叉搜索树如何获取其中第k小的结点
一、思路
二叉搜索树的中序遍历结果正好是从小到大排序好的，按照中序遍历顺序找第k个节点。
例如二叉搜索树（20，10，30，2，11，24，38）中第三小结点的值为11。
二、代码
public class 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 class 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等编程技术的技巧经验分享），若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢，您的支持是我们为您提供帮助的最大动力。
欢迎关注。助您在编程路上越走越好！
