大厂面试：二叉搜索树如何获取其中第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等编程技术的技巧经验分享），若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢，您的支持是我们为您提供帮助的最大动力。

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