题目描述
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
解题思路
- 二叉搜索树是左边比根节点小，右边比根节点大，那么中序遍历就是有序序列
- 因此可以中序遍历进行变形得到我们的结果，我们不需要完整的中序遍历只要能够遍历到第k个值就可以返回结果了，那么怎么实现呢
- 首先看看递归的中序遍历是如下中所示，那么我们要获得第k个数那也就是System打印的第k次，我的想法就是加入一个数组作为传入参数，数组只有一个数据，就是当前节点对应的顺序，从0开始，执行到System的时候将其加1表示当前的位置，然后用这个数值和k比较是否相等，如果相等那就代表找到了这个数字就该结束了，没找到那就要继续执行就是包括右子树遍历了
- 所以在对中序遍历进行修改的时候需要声明一个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;
}
}
