题目描述

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

解题思路

1. 二叉搜索树是左边比根节点小，右边比根节点大，那么中序遍历就是有序序列
2. 因此可以中序遍历进行变形得到我们的结果，我们不需要完整的中序遍历只要能够遍历到第k个值就可以返回结果了，那么怎么实现呢
3. 首先看看递归的中序遍历是如下中所示，那么我们要获得第k个数那也就是System打印的第k次，我的想法就是加入一个数组作为传入参数，数组只有一个数据，就是当前节点对应的顺序，从0开始，执行到System的时候将其加1表示当前的位置，然后用这个数值和k比较是否相等，如果相等那就代表找到了这个数字就该结束了，没找到那就要继续执行就是包括右子树遍历了
4. 所以在对中序遍历进行修改的时候需要声明一个TreeNode的target变量用来存储递归返回结果，整体代码如下

中序遍历代码

private static void inorder(TreeNode root) {
    if (root.left != null) inorder(root.left);
    System.out.println(root.val);
    if (root.right != null) inroder(root.right);
}

源代码实现

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

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

    }

}
*/
public class Solution {
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        if(pRoot==null || k== 0) return null;
        int[] temp = new int[1];
        temp[0] = 0;
        return inorder(pRoot, k, temp);
    }
    
    private static TreeNode inorder(TreeNode root, int k, int[] temp) {
        TreeNode target = null;
        if (root.left != null) target = inorder(root.left, k,  temp);
        temp[0]++;
        if (temp[0]==k) return root;
        if (target==null && root.right !=null) {
            target = inorder(root.right, k, temp);
        }
        return target;
    }
}