题目链接

---

题目描述

给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

解题思路：

• 二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序
• 按照中序遍历顺序找到第k个结点就是结果

/**
 * @author: hyl
 * @date: 2019/08/15
 **/
public class Que62 {

    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }


    //全部遍历,返回一个new的值
    TreeNode KthNode(TreeNode pRoot, int k) {

        if (pRoot == null || k < 1){
            return null;
        }

        List<Integer> list = new ArrayList<>();

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);

        while (!queue.isEmpty()){
            TreeNode node = queue.poll();

            list.add(node.val);

            if (node.left != null){
                queue.add(node.left);
            }

            if (node.right != null){
                queue.add(node.right);
            }

        }

        if (k > list.size()){
            return null;
        }

        Collections.sort(list);

        return new TreeNode(list.get(k));

    }


    int index = 0;
    //叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。
    TreeNode KthNode1(TreeNode pRoot, int k) {



        if (pRoot != null){
            TreeNode node = KthNode1(pRoot.left, k);
            if (node != null){
                return node;
            }

            index ++;

            if (index == k){
                return pRoot;
            }

            node = KthNode1(pRoot.right,k);
            if (node != null){
                return node;
            }
        }

        return null;

    }

}

---

代码地址：
https://github.com/HanYLun/jianzhiOffer/blob/master/Solution/src/Que62.java

---

文章为DavidHan原创,如果文章有错的地方欢迎指正，大家互相交流。