在剑指offer有个求“二叉搜索树的第k个节点（从小到大）”问题。利用BST的性质，直接递归中序遍历即可。但是得到的结果总是null。例图如下：
原来的代码如下：
public class Test { TreeNode KthNode(TreeNode pRoot, int k) { if(pRoot==null || k<=0) return null; int[] array=new int[2]; array[0]=k; TreeNode ansNode=null; return findKth(pRoot,array); } TreeNode findKth(TreeNode pRoot, int[] array) { if(pRoot==null ) return null; findKth(pRoot.left,array); array[1]++; if(array[0]==array[1]) return pRoot; findKth(pRoot.right,array); return null; } public static void main(String[] args) { TreeNode node5=new TreeNode(5); TreeNode node3=new TreeNode(3); TreeNode node7=new TreeNode(7); TreeNode node2=new TreeNode(2); TreeNode node4=new TreeNode(4); TreeNode node6=new TreeNode(6); TreeNode node8=new TreeNode(8); node5.left= node3; node5.right=node7; node3.left= node2; node3.right=node4 ; node7.left=node6 ; node7.right= node8; node2.left= null; node2.right=null; node4.left= null; node4.right=null; node6.left= null; node6.right=null ; node8.left= null; node8.right=null; System.out.println(new Test().KthNode(node5, 1).val); } }这么简洁的代码，最后得到结果却不对。如果用它输出在判断相等的时候直接输出是可以的，但是让它返回就出错。我们分析一下过程，进栈顺序：5-3-2，在2确认2最小后，return pRoot，但是，往下还是要到3和4，即3-4-5-6-7-8，最后访问8的右子树，输出结果肯定是null。是否可以改变递归终止的条件限定呢，比如在找到第k个值后，令array[1]>array[0],开始判断出array[1]>array[0],就返回，但是这样也只能返回null。是否可以用一个空节点变量作为递归参数值，当找到时，将这个节点赋给这个节点变量呢？不行，因为递归是由栈实现的，首先保护现场，然后往下调用，现场保护的节点变量为null，递归回来恢复现场时，仍然是null。
在上面的程序中，可以看到，节点从小到大计数变量是存在一个数组中，这样在某一子递归改变计数变量值，返回到递归中时，仍然保留了改变后的值。其实对对象的修改都可以保留。但是本问题中，查到的对象已经存在，因此不是修改对象的问题。可以考虑建立一个只有元素的节点数组作为参数。这时，对数组元素的修改将一直存在。其实，只要找到第k大元素，从现有的栈返回即可，不需要继续加深栈的深度，所以当nodeArray[0]!=null时，直接返回；具体完整实现如下：
public class Demo { TreeNode KthNode(TreeNode pRoot, int k) { if(pRoot==null || k<=0) return null; int[] array=new int[2]; array[0]=k; TreeNode[] nodeArray=new TreeNode[1]; findKth(pRoot,array,nodeArray); return nodeArray[0]; } TreeNode findKth(TreeNode pRoot, int[] array, TreeNode[] nodeArray) { if(pRoot==null || nodeArray[0]!=null) return null; findKth(pRoot.left,array,nodeArray); array[1]++; if(array[0]==array[1]) nodeArray[0]=pRoot; findKth(pRoot.right,array,nodeArray); return null; } public static void main(String[] args) { TreeNode node5=new TreeNode(5); TreeNode node3=new TreeNode(3); TreeNode node7=new TreeNode(7); TreeNode node2=new TreeNode(2); TreeNode node4=new TreeNode(4); TreeNode node6=new TreeNode(6); TreeNode node8=new TreeNode(8); node5.left= node3; node5.right=node7; node3.left= node2; node3.right=node4 ; node7.left=node6 ; node7.right= node8; node2.left= null; node2.right=null; node4.left= null; node4.right=null; node6.left= null; node6.right=null ; node8.left= null; node8.right=null; System.out.println(new Demo().KthNode(node5, 1).val); } }
